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?

 

分析

 

这个题目是一个计算n层阶梯情况下，走到顶端的路径种数（要求每次只能上1层或者2层阶梯）。 这是一个动态规划的题目：

n = 1 时  ways = 1；

n = 2 时  ways = 2；

n = 3 时  ways = 3；

…

n = k 时  ways = ways[k-1] + ways[k-2]；

 

明显的，这是著名的斐波那契数列问题。有递归和非递归两种方式求解

Solving this problem by recursion ,we will do a lot of same recursion. Example: F(10)=F(9)+F(8); F(9)=F(8)+F(7); we calculate F(8) twice,when n is large,this will increase as a rate of n's exponent.

So a more efficient way to solve this problem is from Bottom to Top. Calculate F(0) ,F(1); then F(2).........

（n >= 3)时，只要保存dp[n-1]和dp[n-2]就够了，没必要保存前面的值

1 class Solution { 2 public: 3     int climbStairs(int n) { 4         int dp[3],temp; 5         dp[0] = 0; 6         dp[1] = 1; 7         dp[2] = 2; 8         if(n <= 2) 9             return dp[n];10         for(int i = 3; i <= n; i++){11             temp = dp[1] + dp[2];12             dp[1] = dp[2];13             dp[2] = temp;14         }15         return dp[2];16     }17 };