-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathClimbing Stairs.py
165 lines (121 loc) · 4.54 KB
/
Climbing Stairs.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
"""
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step 2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
Submission Result: Wrong Answer More Details
Input:
6
Output:
11
Expected:
13
"""
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
combinations = 0
runningTotal = 0
# check for the number of two-steps
for x in range(n):
# multiply the counter by two to account for the current value of two-steps
runningTotal = 2 * x
if runningTotal == n:
# if we've reached the limit with the two-steps then add to our
# found combinations
combinations += 1
# check for the number of two-steps
for y in range(n + 1):
# set the runningTotal to the value of two-steps and current single-steps
runningTotal = ((x * 2) + y)
# if we've reached the limit add the occurance and the varients
# (same values different placement)
if runningTotal == n:
if y!=0:
# add a found solution when y is not zero
combinations += 1
# when our x counter is not zero add the varients
if (x != 0) and ((x * 2) != n):
# Grab all the other positions that the current solution can be
# configured as, minus the one that we've already found
combinations += ((x + y) -1)
return(combinations)
def climbStairs_n_print(self, n):
"""
:type n: int
:rtype: int
"""
combinations = 0
runningTotal = 0
testArray = []
# check for the number of two-steps
for x in range(n):
# multiply the counter by two to account for the current value of two-steps
runningTotal = 2 * x
if x != 0:
for i in range (x):
testArray.append(2)
if runningTotal == n:
# if we've reached the limit with the two-steps then add to our
# found combinations
combinations += 1
print("testArray",testArray)
testArray = []
# check for the number of two-steps
for y in range(n + 1):
# set the runningTotal to the value of two-steps and current single-steps
runningTotal = ((x * 2) + y)
if (y != 0) and (((x * 2) + y) <= n):
testArray.append(1)
# if we've reached the limit add the occurance and the varients
# (same values different placement)
if runningTotal == n:
if y!=0:
# add a found solution when y is not zero
combinations += 1
print("testArray",testArray)
testArray = []
# when our x counter is not zero add the varients
if (x != 0) and ((x * 2) != n):
# Grab all the other positions that the current solution can be
# configured as, minus the one that we've already found
combinations += ((x + y) -1)
return(combinations)
answer = Solution()
"""
testData = 2
print("testData = ", testData)
print("Combinations = ", answer.climbStairs(testData))
testData = 3
print("testData = ", testData)
print("Combinations = ", answer.climbStairs(testData))
testData = 4
print("testData = ", testData)
print("Combinations = ", answer.climbStairs(testData))
testData = 5
print("testData = ", testData)
print("Combinations = ", answer.climbStairs(testData))
"""
testData = 6
print("testData = ", testData)
print("Combinations = ", answer.climbStairs_n_print(testData))
"""
testData = 10
print("testData = ", testData)
print("Combinations = ", answer.climbStairs(testData))
testData = 100
print("testData = ", testData)
print("Combinations = ", answer.climbStairs(testData))
"""