递推算法及解题套路

数学归纳法
step 1: 验证k0成立
step 2: 验证如果ki成立，那么ki+1也成立
step 3: 联合step1与step2，证明由k0->kn成立

如何解决递推问题

1.确定递推状态

一个函数符号f(x)，外加这个函数符号的含义描述
一般函数所对应的值，就是要求解的值

2.确定递推公式（ki->ki+1）

确定f(x)究竟依赖于哪些f(y)的值

3.分析边界条件（k0）

4.程序实现

递归 || 循环

70. 爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        vector<int> f(n + 1);
        f[0] = 1, f[1] = 1;
        for(int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; 
        return f[n];
    }
};

746. 使用最小花费爬楼梯

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        cost.push_back(0);
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i <= n; i++) dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        return dp[n];
    }
};

120. 三角形最小路径和

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> dp;
        for(int i = 0; i < 2; i++) dp.push_back(vector<int> (n));
        for(int i = 0; i < n; i++) dp[(n - 1) % 2][i] = triangle[n - 1][i];
        for(int i = n - 2; i >= 0; --i){
            int ind = i % 2;
            int next_ind = !ind;
            for(int j = 0; j <= i; j++){
                dp[ind][j] = min(dp[next_ind][j], dp[next_ind][j + 1]) + triangle[i][j];
            }
        }
        return dp[0][0];

    }
};

53. 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        for(int i = 1; i < nums.size(); i++) nums[i] += nums[i - 1];
        int pre = 0, ans = INT_MIN;
        for(auto x : nums) {
            ans = max(x - pre, ans);
            pre = min(x, pre);
        }
        return ans;
    }
};

122. 买卖股票的最佳时机 II

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); i++){
            if(prices[i] > prices[i - 1]) {
                ans += prices[i] - prices[i - 1];
            }
        }
        return ans;
    }
};

198. 打家劫舍

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp;
        for(int i = 0; i < n; i++) dp.push_back(vector<int>(2));
        dp[0][0] = 0; dp[0][1] = nums[0];
        for(int i = 1; i < n; i++){
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + nums[i];
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};

322. 零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1);
        for(int i = 1; i <= amount; i++) dp[i] = -1;
        for(int i = 1; i <= amount; i++){
            for(auto x : coins){
                if(i < x) continue;
                if(dp[i - x] == -1) continue;
                if(dp[i] == -1 || dp[i] > dp[i - x] + 1) dp[i] = dp[i - x] + 1;
            }
        }
        return dp[amount];
    }
};

300. 最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size());
        int ans = 0;
        for(int i = 0; i < nums.size(); i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[j] >= nums[i]) continue;
                dp[i] = max(dp[i], dp[j] + 1); 
            }
            ans = max(dp[i], ans);
        }
        return ans;
    }
};