leetcode第70题：70. Climbing Stairs
这道题可以拆分为：到第\(n\)级楼梯的爬法等于到到第\(n-1\)级楼梯的爬法加上到第\(n-2\)级楼梯的爬法。
动态规划
1： 使用递推的办法：
def climbingStairs(self, n):
f = [0 for _ in range(n+1)]
f[0] = 1
f[1] = 1
for i in range(2, n + 1):
f[i] = f[i-1] + f[i-2]
return f[n]
2: 非记忆化递归
会超时，因为没有记住以前的答案，每次都要重复求解
def climbingStairs(self, n):
def numOfSolutions(n):
if n <= 1:
return 1
return numOfSolutions(n-1) + numOfSolutions(n-2)
return numOfSolutions(n)
3: 记忆化递归
每次求解的值都保存下来，这样下一步的时候就不要重复计算，所以比非记忆化递归快
def climbingStairs(self, n):
f_ = [0 for _ in range(n+1)]
def numOfSolutions(n):
if n <= 1: return 1
if f_[n] > 0: return f_[n] # if already calc, then remember it
f_[n] = numOfSolutions(n-1) + numOfSolutions(n-2)
return f_[n]
return numOfSolutions(n)
4: constant变量递推
上面的递推解法里面，第\(i\)步的结果跟前面两步有关，而最终我们不要中间的结果，只要第\(n\)步的结果。所以我们可以使用constant变量来压缩空间。
def climbingStairs(self, n):
two = 1
one = 1
curr = 1
for i in range(2, n + 1):
curr = two + one
two = one
one = curr
return curr