五部曲（代码随想录）

1.确定 dp 数组以及下标含义
2.确定递推公式
3.确定 dp 数组初始化
4.确定遍历顺序
5.debug

入门题

1.斐波那契数

在这里插入图片描述

思路

1.f[i]：第 i 个数的值
2.f[i] = f[i - 1] + f[i - 2]
3.f[0] = 0, f[1] = 1
4.顺序遍历
5.记得特判 n == 0 的时候，因为初始化了 f[1]

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

2.爬楼梯

在这里插入图片描述

思路

每次可以从下面一个台阶或者下面两个台阶处上来

1.f[i]：爬到第 i 阶楼梯有多少种方法
2.f[i] = f[i - 1] + f[i - 2]
3.f[0] = 1, f[1] = 1
4.顺序遍历

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

3.使用最小花费爬楼梯

在这里插入图片描述

思路

可以从 0 或 1 处开始爬楼梯，需要爬到第 n 阶楼梯

1.f[i]：爬到第 i 阶楼梯需要的最小花费
2.f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2)
3.f[0] = 0, f[1] = 0
4.顺序遍历

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

4.不同路径

在这里插入图片描述

思路

1.f[i][j]: 走到 (i, j) 总共的路径
2.f[i][j] = f[i - 1][j] + f[i][j - 1]
3.f[i][1] = 1, f[1][i] = 1
4.顺序遍历

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

5.不同路径 II

在这里插入图片描述

思路

1.f[i][j]: 走到 (i, j) 总共的路径
2.f[i][j] = f[i - 1][j] + f[i][j - 1]
3.f[i][0] = 1, f[0][i] = 1, 其他 = 0
4.顺序遍历

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size();
        int m = obstacleGrid[0].size();
        vector<vector<int>> f(n, vector<int>(m, 0));
        for(int i = 0; i < n && !obstacleGrid[i][0]; i++) f[i][0] = 1;
        for(int i = 0; i < m && !obstacleGrid[0][i]; i++) f[0][i] = 1;
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                if(!obstacleGrid[i][j]){
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }
        return f[n - 1][m - 1];
    }
};

6.整数拆分

在这里插入图片描述

思路

1.f[i]: 拆数字 i 可得到的最大乘积
2.拆分成 j * (i - j) 或 j * f[i - j]，f[i] = max(f[i], max(j * (i - j), j * [i - j]))
3.f[0] = 0, f[1] = 1
4.顺序遍历

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

7.不同的二叉搜索树

在这里插入图片描述

思路

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

1.f[i]: 由 1 到 i 个节点的二叉搜索树个数
2.f[i] += f[j - 1] * f[i - j]
3.f[0] = 1
4.顺序遍历

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

背包问题

1.01背包问题

在这里插入图片描述

思路

1.f[i][j]: 前 i 个物品在容量为 j 的情况下的最大价值
2.f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])
3.全部 = 0
4.顺序遍历

#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int f[N][N], v[N], w[N];
int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
        	// 不选
            f[i][j] = f[i - 1][j];
            // 选
            if(v[i] <= j) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    printf("%d", f[n][m]);
    return 0;
}

// 滚动数组优化
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int f[N], v[N], w[N];
int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= v[i]; j--){
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    printf("%d", f[m]);
    return 0;
}

2.分割等和子集

在这里插入图片描述

思路

分割成两个等和子集，即找到是否存在和为 sum / 2 的子集，转化为 01 背包，背包容量为 sum / 2

1.f[j]: 背包容量为 i，放入物品后的最大重量
2.f[j] = max(f[j], f[j - nums[i]] + nums[i])
3.全部 = 0
4.倒序遍历

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), sum = 0;
        for(int i = 0; i < n; i++) sum += nums[i];
        if(sum % 2) return false;
        vector<int> f(10001, 0);
        for(int i = 0; i < n; i++){
            for(int j = sum / 2; j >= nums[i]; j--){
                f[j] = max(f[j], f[j - nums[i]] + nums[i]);
                if(f[j] == sum / 2) return true;
            }
        }
        return false;
    }
};

3.最后一块石头的重量 II

在这里插入图片描述

思路

尽可能分成两堆重量相同，使得相撞后重量最小

1.f[j]: 容量为 j 的背包，最大价值
2.f[j] = max(f[j], f[j - stones[i]] + stones[i])
3.全部 = 0
4.倒序遍历

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size(), sum = 0;
        for(int i = 0; i < n; i++) sum += stones[i];
        vector<int> f(1501, 0);
        for(int i = 0; i < n; i++){
            for(int j = sum / 2; j >= stones[i]; j--){
                f[j] = max(f[j], f[j - stones[i]] + stones[i]);
            }
        }
        return (sum - f[sum / 2]) - f[sum / 2];
    }
};

4.目标和

在这里插入图片描述

思路

pos - neg = tar 得 pos - (sum - pos) = tar 得 pos = (sum + tar) / 2
转换为背包容量为 pos，有多少种情况装满
无解的情况：pos 为奇数，tar 的绝对值大于 sum
只要搞到 nums[i]，凑成 f[j] 就有 f[j - nums[i]] 种方法。
例如：f[j]，j 为5，
已经有一个1（nums[i]）的话，有 f[4]种方法 凑成 容量为5的背包。
已经有一个2（nums[i]）的话，有 f[3]种方法 凑成 容量为5的背包。
已经有一个3（nums[i]）的话，有 f[2]中方法 凑成 容量为5的背包
已经有一个4（nums[i]）的话，有 f[1]中方法 凑成 容量为5的背包
已经有一个5（nums[i]）的话，有 f[0]中方法 凑成 容量为5的背包
那么凑整 f[5] 有多少方法呢，也就是把 所有的 f[j - nums[i]] 累加起来。

1.f[j]：填满 j 背包有多少种情况
2.f[j] += f[j - nums[i]]
3.f[0] = 1，其他 = 0
4.倒序遍历

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size(), sum = 0;
        for(int i = 0; i < n; i++) sum += nums[i];
        if((sum + target) % 2 || abs(target) > sum) return 0;
        int pos = (sum + target) / 2;
        vector<int> f(pos + 1, 0);
        f[0] = 1;
        for(int i = 0; i < n; i++){
            for(int j = pos; j >= nums[i]; j--){
                f[j] += f[j - nums[i]];
            }
        }
        return f[pos];
    }
};

5.一和零

在这里插入图片描述

思路

可以等价为两个 01 背包，一个装 0，一个装 1

1.f[i][j]: 最多有 i 个 0 和 j 个 1 的最长子集大小
2.f[i][j] = max(f[i][j], f[i - zero][j - one] + 1)
3.全部 = 0
4.倒序遍历

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
        for(auto str : strs){
            int zero = 0, one = 0;
            for(int i = 0; i < str.size(); i++){
                if(str[i] == '0') zero++;
                else one++;  
            }
            for(int i = m; i >= zero; i--){
                for(int j = n; j >= one; j--){
                    f[i][j] = max(f[i][j], f[i - zero][j - one] + 1);
                }
            }
        }
        return f[m][n];
    }
};

6.完全背包

在这里插入图片描述
在这里插入图片描述

思路

01 背包是一个物品只能选一个，所有滚动数组要倒序遍历，完全背包则是一个物品可以选无限个，所以滚动数组正序遍历即可，先遍历物品或者背包容量都可以，因为与顺序无关

#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int f[N], v[N], w[N];
int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d%d", &v[i], &w[i]);
    for(int i = 0; i < n; i++){
        for(int j = v[i]; j <= m; j++){
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    printf("%d", f[m]);
    return 0;
}

7.零钱兑换 II

在这里插入图片描述
在这里插入图片描述

思路

先遍历物品，再遍历背包容量是组合数，因为物品顺序是有序的
先遍历背包容量，再遍历物品时排列数，因为物品是无序的

1.f[j]: 容量为 j 的背包有多少种组合情况
2.f[j] += f[j - coins[i]]
3.f[0] = 1，其他 = 0
4.先物品，再背包，顺序遍历

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> f(amount + 1, 0);
        f[0] = 1;
        // 遍历物品
        for(int i = 0; i < n; i++){
            // 遍历背包
            for(int j = coins[i]; j <= amount; j++){
                f[j] += f[j - coins[i]];
            }
        }
        return f[amount];
    }
};

8.组合总和 Ⅳ

在这里插入图片描述
在这里插入图片描述

思路

求的是排列数，那就先遍历背包，再遍历物品，要特判总和大于 INT32_MAX 的情况

1.f[j]: 背包容量为 j 的排列情况数量
2.f[j] += f[j - nums[i]]
3.f[0] = 1，其他 = 0
4.先背包，再物品，顺序遍历

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> f(target + 1, 0);
        f[0] = 1;
        for(int j = 0; j <= target; j++){
            for(int i = 0; i < n; i++){
                if(nums[i] <= j && f[j] < INT32_MAX - f[j - nums[i]]){
                    f[j] += f[j - nums[i]];
                }
            }
        }
        return f[target];
    }
};

9.爬楼梯

在这里插入图片描述
在这里插入图片描述

思路

求的是排列数，先背包，再物品

1.f[j]: 容量为 j 的背包，有多少种排列情况
2.f[j] += f[j - i]
3.f[0] = 1，其他 = 0
4.先背包，再物品，顺序遍历

#include<iostream>
using namespace std;
const int N = 50;
int f[50];
int n, m;

int main(){
    scanf("%d%d", &n, &m);
    f[0] = 1;
    for(int j = 0; j <= n; j++){
        for(int i = 1; i <= m; i++){
            if(j >= i) f[j] += f[j - i];
        }
    }
    printf("%d", f[n]);
    return 0;
}

10.零钱兑换

在这里插入图片描述

思路

求的是硬币的最小个数，与顺序无关，不影响硬币的个数，排列组合都可以

1.f[j]: 容量为 j 的背包，物品最少数量
2.f[j] = min(f[j], f[j - nums[i]] + 1)
3.f[0] = 0，其他 = 1e9
4.都可以，顺序遍历

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> f(amount + 1, 1e9);
        f[0] = 0;
        for(int i = 0; i < n; i++){
            for(int j = coins[i]; j <= amount; j++){
                f[j] = min(f[j], f[j - coins[i]] + 1);
            }
        }
        return f[amount] == 1e9 ? -1 : f[amount];
    }
};

11.完全平方数

在这里插入图片描述

思路

求的完全平方数的最少数量，与顺序无关，排列组合都可以

1.f[j]：背包容量为 j 的最少物品数
2.f[j] = min(f[j], f[j - i * i] + 1)
3.f[0] = 0，其他 = 1e9
4.都可以，顺序遍历

class Solution {
public:
    int numSquares(int n) {
        int m = sqrt(n);
        vector<int> f(n + 1, 1e9);
        f[0] = 0;
        for(int i = 1; i <= m; i++){
            for(int j = i * i; j <= n; j++){
                f[j] = min(f[j], f[j - i * i] + 1);
            }
        }
        return f[n];
    }
};

12.单词拆分

在这里插入图片描述
在这里插入图片描述

思路

如果确定 f[i] 是 true，且 [i, j] 这个区间的子串出现在字典里，那么 f[i] 一定是 true
所以递推公式是 if([i, j] 这个区间的子串出现在字典里 && f[i]是true) 那么 dp[j] = true
求的是排列数

1.f[j]: 长度为 j 的字符串是否可以拆分为字典里出现的单词
2.if([i, j] 这个区间的子串出现在字典里 && f[i]是true) 那么 dp[j] = true
3.f[0] = true，其他 = false
4.先背包，再物品，顺序遍历

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 存储在无序哈希表中，方便查找
        unordered_set<string> us(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> f(n + 1, false);
        f[0] = true;
        for(int j = 1; j <= n; j++){
            for(int i = 0; i < j; i++){
                // 起始位置，截取的个数
                string t = s.substr(i, j - i);
                if(us.find(t) != us.end() && f[i]){
                    f[j] = true;
                }
            }
        }
        return f[n];
    }
};

13.携带矿石资源

在这里插入图片描述
在这里插入图片描述

思路

多重背包，类似 01 背包，不过就是物品数量变多了

1.f[j]: 背包容量为 j 的最大价值
2.f[j] = max(f[j], f[j - z * w[i]] + z * v[i])
3.全部 = 0
4.倒序遍历

#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int w[N], v[N], k[N];
int f[N];
int c, n;

int main(){
    scanf("%d%d", &c, &n);
    for(int i = 0; i < n; i++) scanf("%d", &w[i]);
    for(int i = 0; i < n; i++) scanf("%d", &v[i]);
    for(int i = 0; i < n; i++) scanf("%d", &k[i]);
    for(int i = 0; i < n; i++){
        for(int j = c; j >= w[i]; j--){
            for(int z = 1; z <= k[i] && j >= z * w[i]; z++){
                f[j] = max(f[j], f[j - z * w[i]] + z * v[i]);
            }
        }
    }
    printf("%d", f[c]);
    return 0;
}

打家劫舍

1.打家劫舍

在这里插入图片描述

思路

如果偷第 i 个房屋，则不可以偷第 i - 1 个房屋，可以偷第 i - 2 个房屋

1.f[i]: 下标为 i 之内的房屋可以偷盗的最大金额
2.f[i] = max(f[i - 1], f[i - 2] + nums[i])
3.f[0] = nums[0], f[1] = max(nums[0], nums[1])
4.顺序遍历

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

2.打家劫舍 II

在这里插入图片描述

思路

头尾的房屋不可以同时偷，分两种情况，偷头和头尾，然后比大小

1.f[i]: 下标为 i 之内的房屋可以偷盗的最大金额
2.f[i] = max(f[i - 1], f[i - 2] + nums[i])
3.f[0] = nums[0], f[1] = max(nums[0], nums[1])
4.顺序遍历，倒序遍历

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

3.打家劫舍 III

在这里插入图片描述
在这里插入图片描述

思路

偷当前节点，就不能偷它的子节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> f(TreeNode* cur){
        if(cur == NULL) return {0, 0};
        vector<int> left = f(cur -> left);
        vector<int> right = f(cur -> right);
        int res1 = cur -> val + left[0] + right[0];
        int res2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {res2, res1};
    }
    
    int rob(TreeNode* root) {
        vector<int> res = f(root);
        return max(res[0], res[1]);
    }
};

买卖股票

1.买卖股票的最佳时机

在这里插入图片描述

思路

只能买卖一次，所以买入股票时，利润只能是 -1 * prices[i]

1.f[i][0]：第 i 天持有股票所得的最大利润，f[i][0]：第 i 天不持有股票所得的最大利润
2.f[i][0] = max(f[i - 1][0], -1 * prices[i]), f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i])
3.f[0][0] = -1 * prices[0], f[0][1] = 0，其他 = 0
4.正序遍历

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(2, 0));
        f[0][0] = -1 * prices[0], f[0][1] = 0;
        for(int i = 1; i < n; i++){
            f[i][0] = max(f[i - 1][0], -1 * prices[i]);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);
        }
        return f[n - 1][1];
    }
};

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

在这里插入图片描述
在这里插入图片描述

思路

股票可以多次买卖，所以买入股票的时候，可能会有之前的利润，即 f[i - 1][1] - prices[i]

1.f[i][0]: 第 i 天持有股票的最大利润，f[i][1]: 第 i 天不持有股票的最大利润
2.f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i]), f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i])
3.f[0][0] = -1 * prices[0], f[0][1] = 0
4.顺序遍历

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(2, 0));
        f[0][0] = -1 * prices[0], f[0][1] = 0;
        for(int i = 1; i < n; i++){
            f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i]);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);
        }
        return f[n - 1][1];
    }
};

3.买卖股票的最佳时机 III

在这里插入图片描述
在这里插入图片描述

思路

1.f[i][0]：不操作，f[i][1]：第一次持有股票的最大利润，f[i][2]：第一次不持有股票的最大利润，f[i][3]：第二次持有股票的最大利润，f[i][4]：第二次不持有股票的最大利润
2.f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i]), f[i][2] = max(f[i - 1][2], f[i - 1][1] + prices[i]), f[i][3] = max(f[i - 1][3], f[i - 1][2] - prices[i]), f[i][4] = max(f[i - 1][4], f[i - 1][3] + prices[i])
3.f[0][1] = -1 * prices[0], f[0][2] = 0, f[0][3] = -1 * prices[0], f[0][4] = 0，其他 = 0
4.顺序遍历

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(5, 0));
        f[0][1] = -1 * prices[0], f[0][2] = 0;
        f[0][3] = -1 * prices[0], f[0][4] = 0;
        for(int i = 1; i < n; i++){
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i]);
            f[i][2] = max(f[i - 1][2], f[i - 1][1] + prices[i]);
            f[i][3] = max(f[i - 1][3], f[i - 1][2] - prices[i]);
            f[i][4] = max(f[i - 1][4], f[i - 1][3] + prices[i]);
        }
        return f[n - 1][4];
    }
};

4.买卖股票的最佳时机 IV

在这里插入图片描述

思路

类似上一题，总结规律即可

1.f[i][0]：不操作，f[i][奇数]：买入股票的最大利润，f[i][偶数]：卖出股票的最大利润
2.f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] - prices[i]), f[i][j + 1] = max(f[i - 1][j + 1], f[i - 1][j] + prices[i])
3.for(int i = 1; i < 2 * k; i += 2) f[0][i] = -1 * prices[0]
4.顺序遍历

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(2 * k + 1, 0));
        for(int i = 1; i < 2 * k; i += 2) f[0][i] = -1 * prices[0];
        for(int i = 1; i < n; i++){
            for(int j = 1; j < 2 * k; j += 2){
                f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] - prices[i]);
                f[i][j + 1] = max(f[i - 1][j + 1], f[i - 1][j] + prices[i]);
            }
        }
        return f[n - 1][2 * k];
    }
};

5.买卖股票的最佳时机含冷冻期

在这里插入图片描述

思路

达到买入股票状态（状态一）即：f[i][0]，有两个具体操作：
操作一：前一天就是持有股票状态（状态一），f[i][0] = f[i - 1][0]
操作二：今天买入了，有两种情况
前一天是冷冻期（状态四），f[i - 1][3] - prices[i]
前一天是保持卖出股票的状态（状态二），f[i - 1][1] - prices[i]
那么f[i][0] = max(f[i - 1][0], f[i - 1][3] - prices[i], f[i - 1][1] - prices[i]);

达到保持卖出股票状态（状态二）即：f[i][1]，有两个具体操作：
操作一：前一天就是状态二
操作二：前一天是冷冻期（状态四）
f[i][1] = max(f[i - 1][1], f[i - 1][3]);

达到今天就卖出股票状态（状态三），即：f[i][2] ，只有一个操作：
昨天一定是持有股票状态（状态一），今天卖出
即：f[i][2] = f[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：f[i][3]，只有一个操作：
昨天卖出了股票（状态三）
f[i][3] = f[i - 1][2];

1.f[i][0]: 持有股票的最大利润，f[i][1]：已经卖出股票的最大利润，f[i][2]: 今天卖出股票的最大利润，f[i][3]：今天是冷冻期的最大利润
2.f[i][0] = max(f[i - 1][0], max(f[i - 1][3] - prices[i], f[i - 1][1] - prices[i])), f[i][1] = max(f[i - 1][1], f[i - 1][3]), f[i][2] = f[i - 1][0] + prices[i], f[i][3] = f[i - 1][2]
3.f[0][0] = -1 * prices[0]，其他 = 0
4.顺序遍历

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(4, 0));
        f[0][0] = -1 * prices[0];
        for(int i = 1; i < n; i++){
            f[i][0] = max(f[i - 1][0], max(f[i - 1][3] - prices[i], f[i - 1][1] - prices[i]));
            f[i][1] = max(f[i - 1][1], f[i - 1][3]);
            f[i][2] = f[i - 1][0] + prices[i];
            f[i][3] = f[i - 1][2];
        }
        return max(f[n - 1][1], max(f[n - 1][2], f[n - 1][3]));
    }
};

6.买卖股票的最佳时机含手续费

在这里插入图片描述

思路

可以在买入的时候交手续费，也可以在卖出的时候交手续费

// 买入的时候交手续费
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(2, 0));
        f[0][0] = -1 * prices[0] - fee;
        for(int i = 1; i < n; i++){
            f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i] - fee);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);
        }
        return f[n - 1][1];
    }
};

// 卖出的时候交手续费
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(2, 0));
        f[0][0] = -1 * prices[0];
        for(int i = 1; i < n; i++){
            f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i]);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i] - fee);
        }
        return f[n - 1][1];
    }
};

子序列

1.最长递增子序列

在这里插入图片描述

思路

注意不是让 f[i] 和 f[j + 1] 比较，而是取 f[j] + 1 的最大值，每次更新以 i 结尾的最大值，用 res 存储最大值，因为不知道以哪个 i 结尾的子序列最大

1.f[i]: 以 i 结尾的最长子序列长度
2.f[i] = max(f[i], f[j] + 1)
3.全部 = 1
4.顺序遍历

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

2.最长连续递增序列

在这里插入图片描述

思路

用 res 存储最大值，因为不知道以哪个 i 结尾的子数组最大

1.f[i]: 以 i 结尾的子数组最大值
2.f[i] = f[i - 1] + 1
3.全部 = 1
4.顺序遍历

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1);
        int res = 1;
        for(int i = 1; i < n; i++){
            if(nums[i] > nums[i - 1]){
                f[i] = f[i - 1] + 1;
            }
            res = max(res, f[i]);
        }
        return res;
    }
};

3.最长重复子数组

在这里插入图片描述

思路

1.f[i][j]: nums1 以 i - 1 结尾，nums2 以 j - 1 结尾的最长重复子数组
2.f[i][j] = f[i -1][j - 1] + 1
3.全部 = 0
4.顺序遍历

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        int res = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    f[i][j] = f[i - 1][j - 1] + 1;
                }
                res = max(res, f[i][j]);
            }
        }
        return res;
    }
};

4.最长公共子序列

在这里插入图片描述

思路

如果 i - 1 和 j - 1 的字符相等，那就直接加一，否则取较大的一方

1.f[i][j]: text1 以 i - 1 结尾，text2 以 j - 1 结尾的最长重复子数组
2.相等，f[i][j] = f[i - 1][j - 1] + 1；不相等，f[i][j] = max(f[i - 1][j], f[i][j - 1])
3.全部 = 0
4.顺序遍历

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        int res = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(text1[i - 1] == text2[j - 1]){
                    f[i][j] = f[i - 1][j - 1] + 1;
                }else{
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
                res = max(res, f[i][j]);
            }
        }
        return res;
    }
};

5.不相交的钱

在这里插入图片描述

思路

最长公共子序列

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        int res = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    f[i][j] = f[i - 1][j - 1] + 1;
                }else{
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
                res = max(res, f[i][j]);
            }
        }
        return res;
    }
};

6.最大子数组和

在这里插入图片描述

思路

分为选之前的数和不选之前的数，做比较取较大值

1.f[i]: 以 i 结尾的最大子数组和
2.f[i] = max(f[i - 1] + nums[i], nums[i])
3.f[0] = nums[0], res = nums[0], 其他 = 0
4.顺序遍历

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

7.判断子序列

在这里插入图片描述

思路

方法1.最长公共子序列
方法2.编辑距离，如果 i - 1 不等于 j - 1，那么就删除 j - 1

1.f[i][j]: s 以 i - 1 结尾，t 以 j - 1 结尾的相同子序列长度
2.相等，f[i][j] = f[i - 1][j - 1] + 1；不相等，f[i][j] = f[i][j - 1]
3.全部 = 0
4.顺序遍历

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(s[i - 1] == t[j - 1]){
                    f[i][j] = f[i - 1][j - 1] + 1;
                }else{
                    f[i][j] = f[i][j - 1];
                }
            }
        }
        return f[n][m] == n;
    }
};

8.不同的子序列

在这里插入图片描述

思路

当 i - 1 和 j - 1 相等时，分为用 j - 1 匹配和不用 j - 1 匹配
当 i - 1 和 j - 1 不相等时，不用 j - 1 匹配

1.以 i - 1 结尾的 t 在以 j - 1 结尾的 s 中出现的次数
2.相等，f[i][j] = (f[i - 1][j - 1] + f[i][j - 1]) % 1000000007；不相等，f[i][j] = f[i][j - 1]
3.for(int i = 0; i <= m; i++) f[0][i] = 1
4.顺序遍历

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = t.size(), m = s.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        for(int i = 0; i <= m; i++) f[0][i] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(t[i - 1] == s[j - 1]){
                    f[i][j] = (f[i - 1][j - 1] + f[i][j - 1]) % 1000000007;
                }else{
                    f[i][j] = f[i][j - 1];
                }
            }
        }
        return f[n][m];
    }
};

9.两个字符串的删除操作

在这里插入图片描述

思路

如果 i - 1 和 j - 1 相同，那就不删除，如果不相同，那就删除操作少的

1.f[i][j]: 以 i - 1 结尾的 word1 和以 j - 1 结尾的 word2 相同最少的删除数
2.相等，f[i][j] = f[i - 1][j - 1]；不相等，f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1
3.for(int i = 0; i <= n; i++) f[i][0] = i，for(int j = 0; j <= m; j++) f[0][j] = j

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        for(int i = 0; i <= n; i++) f[i][0] = i;
        for(int j = 0; j <= m; j++) f[0][j] = j;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(word1[i - 1] == word2[j - 1]){
                    f[i][j] = f[i - 1][j - 1];
                }else{
                    f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
                }
            }
        }
        return f[n][m];
    }
};

10.编辑距离

在这里插入图片描述
在这里插入图片描述

思路

如果相等就不操作，如果不相等，删除元素和添加元素是等价的，取最小的，修改元素就是在上一个状态下加一操作，因为已经初始化了删除一边的操作数，所以删除两个元素只需要加一

1.f[i][j]: 以 i - 1 结尾的 word1 和以 j - 1 结尾的 word2 相同最少操作数
2.相等，f[i][j] = f[i - 1][j - 1]；不相等，f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1
3.for(int i = 0; i <= n; i++) f[i][0] = i，for(int j = 0; j <= m; j++) f[0][j] = j

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        for(int i = 0; i <= n; i++) f[i][0] = i;
        for(int j = 0; j <= m; j++) f[0][j] = j;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(word1[i - 1] == word2[j - 1]){
                    f[i][j] = f[i - 1][j - 1];
                }else{
                    f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
                }
            }
        }
        return f[n][m];
    }
};

11.回文子串

在这里插入图片描述

思路

如果 s[i] 和 s[j] 相等，分三种情况，i == j，那么肯定是回文串；j - i == 1，那么也是回文串；否则就还要判断 s[i +1] 和 s[j - 1]
在这里插入图片描述
因为 i, j 要用到 i + 1, j - 1 的状态，所以一定要从左下到右上遍历

1.f[i][j]: s 的 [i, j] 区间回文子串个数
2.j - i <= 1，f[i][j] = true；f[i + 1][j - 1] == true，f[i][j] = true
3.全部 = false
4.先倒序，再顺序，从坐下到右上

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> f(n, vector<bool>(n, false));
        int res = 0;
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s[i] == s[j]){
                    if(j - i <= 1){
                        res++;
                        f[i][j] = true;
                    }else if(f[i + 1][j - 1] == true){
                        res++;
                        f[i][j] = true;
                    }
                }
            }
        }
        return res;
    }
};

12.最长回文子序列

在这里插入图片描述

思路

如果相等，那就同时加入，如果不相等，那就看加入哪个更长

1.f[i][j]: s 在 [i, j] 内的最长回文子序列长度
2.相等，f[i][j] = f[i + 1][j - 1] + 2；不相等，f[i][j] = max(f[i + 1][j], f[i][j - 1])
3.for(int i = 0; i < n; i++) f[i][i] = 1
4.从左下到右上

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> f(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++) f[i][i] = 1;
        for(int i = n - 1; i >= 0; i--){
            for(int j = i + 1; j < n; j++){
                if(s[i] == s[j]){
                    f[i][j] = f[i + 1][j - 1] + 2;
                }else{
                    f[i][j] = max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return f[0][n - 1];
    }
};
推荐内容
阅读全文
AI总结
# 蓝桥杯 # 算法 # 职场和发展
Logo
GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

cover

颠覆开发效率！国内首个开源微服务编排框架Juggle入驻GitCode

avatar GitCode 开源社区
cover

“盲水印”技术新标杆：blind_watermark加入GitCode

avatar GitCode 开源社区
cover

开源平台GitCode招人啦，大量好岗！

avatar GitCode 开源社区