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?
非常简单的动态规划问题
class Solution(object):
"""
:type n: int
:rtype: int
"""
# def getSum(self,n):
# if n < 0:
# return
# elif n == 0:
# self.sum+=1
# return
# self.getSum(n-1)
# self.getSum(n-2)
# def climbStairs(self, n):
# self.sum = 0
# self.getSum(n)
# return self.sum
# F[k] = F[k-2] + F[k-1]
def climbStairs(self, n):
F = []
for i in range(n+1):
F.append(0)
k = 2
F[1] = F[0] = 1
while k <= n:
F[k] = F[k-1] + F[k-2]
k+=1
return F[n]
