LeetCode70. 爬楼梯

题目

分析

用一维数组 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)

如果本题用回溯呢？

 1 class Solution {
 2 public:
 3     long long res = 0;
 4     void backtracking(int n,vector<int>nums,long long sum){
 5         if(sum == n){
 6             res++;
 7             return;
 8         }
 9         if(sum > n) return;
10         for(int i = 0;i < 2;i++){
11             sum += nums[i];
12             backtracking(n,nums,sum);
13             sum -= nums[i];
14         }
15     }
16     int climbStairs(int n) {
17         vector<int>nums(2);
18         nums[0] = 1;nums[1] = 2;
19         backtracking (n,nums,0);
20         return res;
21     }
22 };

上面代码大约到 n = 28时就超出时长了，回溯的话搜索树会很庞大，耗时长。而动态规划却保存了之前状态。