【題目】
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?
【分析】
一看就是用動態(tài)規(guī)劃，本題與求二叉搜索樹那道類似，但是要簡單些纳决。
d(i) = d(i-1) + d(i-2)
【代碼】
class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
dp = [0, 1, 2]
if n <= 2:
return dp[n]
dp += [0 for i in range (n-2)]
for i in range (3, n + 1):
dp[i] += dp[i-1] + dp[i-2]
return dp[n]
