当前位置：首页 > news >正文

十一、动态规划题目相关

news 来源：原创 2024/5/6 5:04:28

学习来源：
代码随香炉：https://www.programmercarl.com/
labuladong算法：https://labuladong.github.io/algo/

动态规划

动态规划五部曲

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

基础题目

斐波那契数列

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

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

思路：
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯和到第一层楼梯状态推导出来，那么就可以想到动态规划了。

dp[i] = dp[i - 1] + dp[i - 2] 。

需要注意初始化的问题

本题其实就不应该讨论dp[0]的初始化！ dp[1] = 1，dp[2] = 2

遍历顺序一定是从前向后遍历的

// 版本一
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

优化空间复杂度

// 版本二
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};

使用最小花费爬楼梯

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

思路
dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。（注意这里认为是第一步一定是要花费）

选择花费最小的
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

最终结果， dp[n] 与dp[n-1]中比较的那数 ,顶层不需要花费

// 版本一
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size());
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.size(); i++) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
        return min(dp[cost.size() - 1], dp[cost.size() - 2]);
    }
};

一步可以1-m个台阶爬楼梯（背包）

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) { // 把m换成2，就可以AC爬楼梯这道题
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
举例推导dp数组

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

不同路径 II 有障碍物

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
	if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍，直接返回0
            return 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) continue;//有障碍物直接continue
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

在这里插入图片描述

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

不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

在这里插入图片描述

思路：

dp[3]，就是元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。
dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素，从1遍历到i为止。

所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，
j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

dp[0] = 1
顺序遍历两个for循环
举例

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

背包问题

基础理论

二维dp

在这里插入图片描述

01
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

二维dp数组01背包

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
那么可以有两个方向推出来dp[i][j]，
不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)

放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

初始化
首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

在这里插入图片描述

遍历顺序

一维dp (滚动数组)

重点
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。
这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
dp[j - weight[i]] + value[i] 表示容量为 j - 物品i重量的背包加上物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）
此时dp[j]有两个选择，一个是取自己dp[j] 相当于二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，
那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

一维dp数组遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

二维遍历顺序可以颠倒，一维的dp只能先遍历物品，再遍历背包，背包倒叙遍历。
二维dp数组两层数据隔离，因此正遍历无所谓，并且背包物品的先后顺序也可以颠倒。
但是一维dp，是将上一层的数据拷贝到当前层，被背包的正序遍历会将元素重复添加，因此倒序可以只加一次。

01背包

模板：先遍历物品再遍历背包，并且背包容量倒着遍历

分割等和子集（sum/2）是否可以

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.

本题要求集合里能否出现总和为 sum / 2 的子集。

思路：
背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。

dp[j]表示背包总容量是j，最大可以凑成j的子集总和为dp[j]。
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
vector dp(10001, 0);
物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
举例推导dp数组
dp[j]的数值一定是小于等于j的。
如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

在这里插入图片描述

最后一块石头的重量（相等粉碎，求最后最小重量）

在这里插入图片描述

思路：
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

最后dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
结果就是sum-dp[target] - dp[target]

dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。

在这里插入图片描述

目标和（+ -求满足的方法数）

在这里插入图片描述

回溯算法解法：
在这里插入图片描述

01背包解法：
既然为target，那么就一定有 left组合 - right组合 = target。
left + right等于sum，而sum是固定的。
公式来了， left - (sum - left) = target -> left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法。
dp[j] += dp[j - nums[i]]
不考虑nums[i]的情况下，填满容量为j - nums[i]的背包，有dp[j - nums[i]]种方法。
那么只要搞到nums[i]的话，凑成dp[j]就有dp[j - nums[i]] 种方法。

在这里插入图片描述
3. dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品。
dp[j]其他下标对应的数值应该初始化为0，从递归公式也可以看出，dp[j]要保证是0的初始值，才能正确的由dp[j - nums[i]]推导出来。

nums放在外循环，target在内循环，且内循环倒序。

一和零（两个背包最大子集长度）

在这里插入图片描述

思路：
本题中strs 数组里的元素就是物品，每个物品都是一个！
而m 和 n相当于是一个背包，两个维度的背包。

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。

这就是一个典型的01背包！只不过物品的重量有了两个维度而已。

因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
我们讲到了01背包为什么一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
// 遍历背包容量且从后向前遍历！

在这里插入图片描述

完全背包

0-1
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j–) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}

完全
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

}

// 先遍历物品，在遍历背包
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}

零钱兑换（凑成的组合个数）

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

在这里插入图片描述

组合不强调元素之间的顺序，排列强调元素之间的顺序。这和下文讲解遍历顺序息息相关!

dp[j]：凑成总金额j的货币组合数为dp[j]
dp[j] += dp[j - coins[i]];
dp[j] （考虑coins[i]的组合总和）就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。
首先dp[0]一定要为1，dp[0] = 1是递归公式的基础。
下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）

在这里插入图片描述

组合总和IV（其实是排列总和）

在这里插入图片描述

dp[i]: 凑成目标正整数为i的排列个数为dp[i]
dp[i] += dp[i - nums[j]]
1 0
target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。
得到的集合是排列，说明需要考虑元素之间的顺序。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

求装满背包有几种方法，递归公式都是一样的，没有什么差别，但关键在于遍历顺序！

爬楼梯进阶版

改为：一步一个台阶，两个台阶，三个台阶，…，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
1阶，2阶，… m阶就是物品，楼顶就是背包。
每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。
问跳到楼顶有几种方法其实就是问装满背包有几种方法。
此时大家应该发现这就是一个完全背包问题了！

dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
dp[i] += dp[i - j]
dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。
所以需将target放在外循环，将nums放在内循环。

class Solution {
public:
int climbStairs(int n) {
vector dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) { // 遍历背包
for (int j = 1; j <= m; j++) { // 遍历物品
if (i - j >= 0) dp[i] += dp[i - j];
}
}
return dp[n];
}
};

零钱兑换（凑成最少硬币个数）

在这里插入图片描述

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
所以本题并不强调集合是组合还是排列。本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。

完全平方数（和为n的~最小数量）

在这里插入图片描述
思路：
完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

dp[j]：和为j的完全平方数的最少数量为dp[j]
dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);
dp[0]表示和为0的完全平方数的最小数量，那么dp[0]一定是0。
非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。
都是可以

在这里插入图片描述

单词拆分（是否可以多个单词构成）

在这里插入图片描述

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
dp[0]就是递归的根基，dp[0]一定要为true
遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。
本题还有特殊性，因为是要求子串，最好是遍历背包放在外循环，将遍历物品放在内循环。
如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的子串都预先放在一个容器里。

打家劫舍问题

打家劫舍（一排最多金额）

在这里插入图片描述

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
决定dp[i]的因素就是第i房间偷还是不偷。
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]);
dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历
！

在这里插入图片描述

打家劫舍（一圈最多金额）

在这里插入图片描述

对于一个数组，成环的话主要有如下三种情况：
情况一：考虑不包含首尾元素
情况二：考虑包含首元素，不包含尾元素
情况三：考虑包含尾元素，不包含首元素
而情况二和情况三都包含了情况一了，所以只考虑情况二和情况三就可以了。

在这里插入图片描述

打家劫舍（二叉树最多金额）

在这里插入图片描述

本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。

// 下标0：不偷，下标1：偷

// 偷cur
int val1 = cur->val + left[0] + right[0];
// 不偷cur
int val2 = max(left[0], left[1]) + max(right[0], right[1]);

在这里插入图片描述

买卖股票问题

买卖股票

在这里插入图片描述

第一题是只进行一次交易，相当于 k = 1；第二题是不限交易次数，相当于 k = +infinity（正无穷）；第三题是只进行 2 次交易，相当于 k = 2；剩下两道也是不限次数，但是加了交易「冷冻期」和「手续费」的额外条件，其实就是第二题的变种，都很容易处理。

买卖股票的最佳时机（k=1 最大利润）

在这里插入图片描述

动态规划

dp[i][0] 表示第i天持有股票所得最多现金 dp[i][1] 表示第i天不持有股票所得最多现金
其实一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]，这是一个负数。

dp[i][0] = max(dp[i - 1][0], -prices[i])

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来：

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金
即：dp[i - 1][0]
第i天买入股票，所得现金就是买入今天的股票后所得现金
即：-prices[i]

dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

如果第i天不持有股票即dp[i][1]，也可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金
即：dp[i - 1][1]
第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金
即：prices[i] + dp[i - 1][0]

dp[0][0] -= prices[0]; dp[0][1] = 0;
从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的，那么一定是从前向后遍历。

本题中不持有股票状态所得金钱一定比持有股票状态得到的多！
在这里插入图片描述

贪心
在这里插入图片描述

买卖股票的最佳时机 II (k=infinity)

在这里插入图片描述

dp数组的含义：
dp[i][0] 表示第i天持有股票所得现金。
dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来
第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]
第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格即：dp[i - 1][1] - prices[i]

在来看看如果第i天不持有股票即dp[i][1]的情况，依然可以由两个状态推出来
第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]
第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

在这里插入图片描述

买卖股票的最佳时机 III (k=2)

在这里插入图片描述

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

在这里插入图片描述

@买卖股票的最佳时机IV (最多卖k次) 通用

在这里插入图片描述

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max( 今天选择 rest, 今天选择 sell )

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( 今天选择 rest, 今天选择 buy )

使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]
除了0以外，偶数就是卖出，奇数就是买入。 vector<vector> dp(prices.size(), vector(2 * k + 1, 0));
本题和动态规划：123.买卖股票的最佳时机III 最大的区别就是这里要类比j为奇数是买，偶数是卖的状态。
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
初始化
dp[0][0] = 0
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

在这里插入图片描述

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

在这里插入图片描述

dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。

在这里插入图片描述

如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，买入股票所剩现金为负数。

保持卖出股票状态（状态二），第0天没有卖出dp[0][1]初始化为0就行，

今天卖出了股票（状态三），同样dp[0][2]初始化为0，因为最少收益就是0，绝不会是负数。

同理dp[0][3]也初始为0。

从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。

在这里插入图片描述

买卖股票含手续费

在这里插入图片描述
相对于动态规划：122.买卖股票的最佳时机II (k = 无穷)，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的。

在这里插入图片描述

子序列问题

子序列（不连续）

最长递增子序列（最大长度）

在这里插入图片描述

dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。
每一个i，对应的dp[i]（即最长上升子序列）起始大小至少都是1.
j其实就是0到i-1，遍历i的循环在外层，遍历j则在内层

两个for循环嵌套因为中间不连续

在这里插入图片描述

最长公共子序列（两个数组不连续）

在这里插入图片描述
中间元素可以有间隔
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。

if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

v 在这里插入图片描述

不相交的线

在这里插入图片描述

https://leetcode-cn.com/problems/uncrossed-lines/
同最长公共子序列（不连续的）
注意dp的范围 m+1 n+1 注意 for循环的范围作用在dp上返回最后的dp

在这里插入图片描述

子序列（连续）

最长连续递增序列

https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
两个思路动态规划 + 贪心策略不用j 所以不用两层for循环进行遍历

动态规划策略

dp[i]：以下标i为结尾的数组的连续递增的子序列长度为dp[i]。
本题要求连续递增子序列，所以就必要比较nums[i + 1]与nums[i]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。
既然不用j了，那么也不用两层for循环，本题一层for循环就行，比较nums[i + 1] 和 nums[i]。
以下标i为结尾的数组的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。
dp[i + 1]依赖dp[i]，所以一定是从前向后遍历。

贪心策略解法
在这里插入图片描述

最长重复子数组（两个数组公共部分）

在这里插入图片描述

注意题目中说的子数组，其实就是连续子序列。

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！dp[i][0] 和dp[0][j]初始化为0。
外层for循环遍历A，内层for循环遍历B。
同时题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp[i][j]的最大值记录下来。

在这里插入图片描述

最大子序和

在这里插入图片描述

贪心算法：在这里插入图片描述

动态规划：

dp[i]：包括下标i之前的最大连续子序列和为dp[i]

dp[i]只有两个方向可以推出来：
dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
nums[i]，即：从头开始计算当前连续子序列和
一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
            if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
        }
        return result;
    }
};

编辑距离vecvec

判断子序列（存在 2数组不连续）

在这里插入图片描述

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

在这里插入图片描述
3. vector<vector> dp(s.size() + 1, vector(t.size() + 1, 0));
4. 同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右
使用下方代码判断
if (dp[s.size()][t.size()] == s.size()) return true;

在这里插入图片描述

不同的子序列（个数 2数组不连续）!!xx

在这里插入图片描述

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
基本是要分析两种情况
s[i - 1] 与 t[j - 1]相等 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
s[i - 1] 与 t[j - 1] 不相等 dp[i][j] = dp[i - 1][j];

当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。

当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]
3.
dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。dp[i][0]一定都是1
dp[0][j]一定都是0，s如论如何也变成不了t。
4. 所以遍历的时候一定是从上到下，从左到右，这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

标准库头文件
C++ 标准库头文件
此头文件原作为 <stdint.h> 存在于 C 标准库。
uint_64_t

在这里插入图片描述

两个字符串的删除操作(步数，可以删除两个中任意，=)

在这里插入图片描述

思路1
本题和动态规划：1143.最长公共子序列，基本相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

在这里插入图片描述

思路2：

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

vector<vector> dp(word1.size() + 1, vector(word2.size() + 1));
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

所以遍历的时候一定是从上到下，从左到右，
在这里插入图片描述

删除就是位置向右移动一个，数组中的元素不用真正的删除。

编辑距离(a > b最少操作数)

应用 DNA距离

在这里插入图片描述

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
确定递推公式

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    换

if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];

if (word1[i - 1] != word2[j - 1])，此时就需要编辑了

操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离再加上一个操作。
dp[i][j] = dp[i - 1][j] + 1;
操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离再加上一个操作。
dp[i][j] = dp[i][j - 1] + 1;

在这里插入图片描述

操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离加上一个替换元素的操作。
dp[i][j] = dp[i - 1][j - 1] + 1;

if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}

初始化
dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;

同理dp[0][j] = j;

遍历顺序

在这里插入图片描述

回文

回文子串（回文的个数）

在这里插入图片描述

暴力解法
两层for循环，遍历区间起始位置和终止位置，然后判断这个区间是不是回文。

时间复杂度： $O(n^3)$

双指针法
一个元素可以作为中心点，两个元素也可以作为中心点。
在这里插入图片描述

动态规划

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况：

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是回文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

所以dp[i][j]初始化为false。
4 情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。
从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

最长回文子序列（最长）

在这里插入图片描述

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1][j]。
加入s[i]的回文子序列长度为dp[i][j - 1]。
那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}

：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出递推公式是计算不到 i 和j相同时候的情况。
vector<vector> dp(s.size(), vector(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;

在这里插入图片描述