【题目】
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?
【分析】
一看就是用动态规划，本题与求二叉搜索树那道类似，但是要简单些。
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]
网友评论