Leetcode 70. Climbing Stairs

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 };