很经典的动态规划问题:
基本情况为,
当n为0时,0种方法,
当n为1时,1种方法,
当n为2时,2种方法.
给了我们n阶台阶,若我们知道到达[n-1]阶的方法数,和到达[n-2]阶的方法数,并设为n1,n2.
那么到达n阶的方法数即为n1+n2.这很像一个斐波那契数列,只不过起始的数字从1,1变为1,2.
由此我们可以列出状态转移方程
dp[n]=dp[n-1]-dp[n-2]
我们可以写出一个空间复杂度为n的解法
def climbStairs(self, n):
if n == 1:
return 1
res = [0 for i in xrange(n)]
res[0], res[1] = 1, 2
for i in xrange(2, n):
res[i] = res[i-1] + res[i-2]
return res[-1]
当然还可以更pythonic
def climbStairs(self, n):
a = b = 1
for _ in range(n):
a, b = b, a + b
return a
