Description
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?
Example
Given an example n=3 , 1+1+1=2+1=1+2=3
return 3
Notes
这题开始没懂是要干什么，看到tag里的动态规划（Dynamic Programming）和别人的分析，才明白了题意。表面上看是求加和到n能有几种方案，换种方式理解，爬梯子爬到第n层有两种路径，一种是从n-1层爬1步，一种是从n-2层爬2步，所以dp[n]=dp[n-1]+dp[n-2]；而爬到n-1层的方案数是dp[n-1]，爬到n-2层的方案数是dp[n-2]；这样就能看出递归的趋势了。
。。。所以它居然和斐波那契数列有些像，开始真是没明白题意
Solution
class Solution { public: /** * @param n: An integer * @return: An integer */ int climbStairs(int n) { // write your code here int *dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for(int i=2; i<=n; i++){ dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } };其实原先写的是
int climbStairs(int n) { // write your code here if(n>=2) return n; int *dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for(int i=2; i<=n; i++){ dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }
这样dp[0]=0了，不通过。。。 （虽然AC了，但仍不理解为什么dp[0]=1）
