LeetCode OJ：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?

Subscribe to see which companies asked this question

简单的dp问题，代码如下：

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

java版本代码如下所示：

 1 public class Solution {
 2     public int climbStairs(int n) {
 3         if(n < 3) return n;
 4         int dp [] = new int [n+1];
 5         dp[1] = 1;
 6         dp[2] = 2;
 7         for(int i = 3; i <= n; ++i){
 8             dp[i] = dp[i-1] + dp[i-2];
 9         }
10         return dp[n];
11     }
12 }