70. Climbing Stairs

很经典的动态规划问题:
基本情况为,
当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