forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathclimbing-stairs.py
More file actions
executable file
·66 lines (55 loc) · 2.09 KB
/
climbing-stairs.py
File metadata and controls
executable file
·66 lines (55 loc) · 2.09 KB
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
#https://leetcode.com/problems/climbing-stairs/
class Solution(object):
#if there are 13 stairs
#the max two steps are 6, so there can be
#6 two step, 1 one step -> case1
#5 two step, 3 one step -> case2
# ...
#0 two step, 13 one step -> case7
#each case may have more than one way to arrange
#take case2 as example, 22222111. how many combination can it be?
#you can think this as, there are 8 seats you have to choose 3 seats for number 1 to sit on it.
#we call this combination m choose n, thus
#case1 is combination 7 choose 1
#case2 is combination 8 choose 3
# ...
#case7 is combination 13 choose 13
#the calculation of combination is m!/(n!*(m-n)!)
#https://en.wikipedia.org/wiki/Combination
#Efficaiency is O(N), N is the stairs count.
#Space is O(1)
def climbStairs(self, n):
counter = 0
max_two_step = n/2
for two_step in range(max_two_step+1):
one_step = n-two_step*2
combination = self.combination(two_step+one_step, one_step)
counter+=combination
return counter
#combination m choose n
def combination(self, m, n):
def factorial(int_num):
if int_num<0: return None
if int_num==0: return 1
counter = 1
while int_num>=1:
counter*=int_num
int_num-=1
return counter
return factorial(m)/(factorial(n)*factorial(m-n))
#2020/11/9
class Solution(object):
def climbStairs(self, n):
def helper(n):
if n in history: return history[n]
if n==0 or n==1:
history[n] = 1
elif n==2:
return 2
elif n>2:
#combination count of n stairs equals to
#(the combination after you make 1 step as first move) + (the combination after you make 2 steps as first move)
history[n] = helper(n-1) + helper(n-2)
return history[n]
history = {}
return helper(n)