用一维数组 dp[n] 表示爬到 n阶楼顶有多少种爬法，观察规律发现 dp[n] = dp[i-1] + dp[i-2]，就是斐波那契数列。因为爬楼梯每次只能一个或两个台阶
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 vector<int>dp(n+1); 5 if(n == 0) return 1; 6 if(n <= 2) return n; 7 dp[0] = 1;dp[1] = 1;dp[2] = 2; 8 for(int i = 3;i <= n;i++){ 9 dp[i] = dp[i-1] + dp[i-2]; 10 } 11 return dp[n]; 12 } 13 };
时间复杂度O(N)，空间复杂度O(N)
原文：https://www.cnblogs.com/fresh-coder/p/14379697.html