【算法/训练】：动态规划DP
【算法/训练】：动态规划DP
1. 基本概念
动态规划（Dynamic Programming，DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题
动态规划算法与分治法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中 得到原有问题的解，两者的区别在于
- 动态规划经分解后得到的子问题往往 不是相互独立 的。
- 分治算法也可以解决分解后得到的子问题不是相互独立的情况，只是需要对公共子问题进行单独求解，但是这样会使分治法求解问题的复杂度大大提高。
2. 核心思想
🍎 动态规划的核心思想是：将复杂问题分解成小的、互相重叠的子问题，并通过求解子问题来逐步解决原问题。在动态规划中，每个子问题只解决一次，其解一旦计算出来就会被保存起来，如果再次需要这个子问题的解，只是简单地查找已经计算过的结果，而不需要重新计算。这种策略避免了大量的重复计算，从而提高了算法的效率
3. 具体应用 🖊
🌈 动态规划可以应用于许多类型的问题，如路径问题、资源分配问题、背包问题等。一个经典的例子是斐波那契数列，通常用递归方法解决，但递归方法会重复计算许多子问题，而动态规划则通过存储已解决的子问题来避免重复计算
- 例如：斐波那契数列的动态规划实现可以通过创建一个数组来存储每个子问题的解，然后从底部开始计算，直到得到最终结果。这种自底向上的方法避免了递归中的重复计算，提高了效率。
4. 步骤 📑
动态规划的实现通常包括以下几个步骤：
- 定义子问题：将原问题分解为子问题。
- 实现递归解决方案：这通常涉及到编写一个递归函数来解决子问题。
- 优化递归解决方案：通过存储子问题的解（通常是使用数组或哈希表）来避免重复计算。
- 构建动态规划解决方案：使用自底向上的方法，从最简单的子问题开始，逐步构建问题的解决方案。
一、斐波那契数列
1. 第 N 个泰波那契数
思路： 1、状态表示： dp[i] 表示第 i 个泰波拉契数的值 2、状态转移方程： dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; 3、初始化：dp[0] = 0, dp[1] = 1, dp[2] = 1; 4、填表顺序： 从左往右开始填写 5、返回值：dp[n]. 6、优化：空间优化
class Solution {
public:
int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
// dp数组（正常做法）
vector<int> dp(n + 1);
dp[0] = 0, dp[1] = 1, dp[2] = 1;
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
// 空间优化：滚动数组
int p = 0, q = 1, r = 1, s = 0;
for (int i = 3; i <= n; i++)
{
s = p + q + r;
p = q;
q = r;
r = s;
}
return r;
}
};2. 三步问题
思路： 1、状态表示： dp[i] 表示到达第 i 个台阶的上楼方法 2、状态转移方程： dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; 3、初始化：dp[0] = 0, dp[1] = 1, dp[2] = 2, dp[3] = 4; 4、填表顺序： 从左往右开始填写 5、返回值：dp[n]. 6、优化：空间优化（滚动数组和上面类似）
class Solution {
public:
int waysToStep(int n) {
if(n <= 2) return n;
else if(n == 3) return 4;
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i=4;i<=n;i++){
dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;
}
return dp[n] % 1000000007;
}
};3. 使用最小花费爬楼梯
思路： 1、状态表示： 以i位置为终点，dp[i] 表示到达 i 位置的最小花费 2、状态转移方程： dp[i] = min(dp[i - 1] + costs[i - 1], dp[i - 2] + costs[i - 2]) 3、初始化：dp[0] = dp[1] = 0 4、填表顺序： 从左往右开始填写 5、返回值：dp[n].
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
// 以 i 位置为终点
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++)
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
return dp[n];
// 以 i 位置为起点
int n = cost.size();
vector<int> dp(n);
dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
for (int i = n - 3; i >= 0; i--)
dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];
return min(dp[0], dp[1]);
}
};4. 解码方法
思路： 1、状态表示：dp[i] 表示以i位置为结尾解法方法的总数 2、状态转移方程：
- 根据最近一步来划分问题（a表示原字符串第i个位置的字符，b表示第i -1位置的字符）
- s[ i ] 单独解码，成功（1≤ a ≤ 9）--> dp[ i - 1 ]， 失败则是0
- s[ i - 1] 和 s[ i ]解码，成功（10≤ b * 10 + a ≤ 26【不是1-26的原因，避免出现前导0】）--> dp[ i - 2 ]， 失败则是0
- dp[ i ] = dp[ i - 1] + dp[ i - 2] (注意需要按照上面条件)
3、初始化：
- dp[0] = 0 或者 1 （1≤ a ≤ 9）
- dp[1] = 0, 1, 2
4、填表顺序： 从左往右开始填写 5、返回值：dp[n - 1]
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
// 1. 创建 dp 表
vector<int> dp(n);
// 2. 初始化
dp[0] = s[0] != '0';
if (n == 1) return dp[0]; // 处理边界情况
if (s[0] != '0' && s[1] != '0') dp[1] += 1; //第二个数字表示一个字符
int t = (s[0] - '0') * 10 + s[1] - '0'; //前两个位置表示得数字
if (t >= 10 && t <= 26) dp[1] += 1; // 两个数字表示一个字符
// 3. 填表
for (int i = 2; i < n; i++)
{
if (s[i] != '0') dp[i] += dp[i - 1]; //处理单独编码情况
int t = (s[i - 1] - '0') * 10 + s[i] - '0'; //前两个位置表示得数字
if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
}
// 4. 返回值
return dp[n - 1];
/* ----------- 优化代码 --------- */
// 1. 创建 dp 表
vector<int> dp(n + 1);
// 2. 初始化
dp[0] = 1; //保证后面填表正确
dp[1] = s[1 - 1] != '0';
// 3. 填表
for (int i = 2; i <= n; i++)
{
if (s[i - 1] != '0') dp[i] += dp[i - 1]; //处理单独编码情况
int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0'; //前两个位置表示得数字
if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
}
// 4. 返回值
return dp[n];
}
};二、路径类
1. 不同路径
题目描述：一个机器人位于一个 m x n 网格的左上角 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角求，总共有多少条不同的路径？
思路： 1、状态表示：dp[i][j] 表示：走到[i, j]位置，一共有多少种方法 2、状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1];（由于只能往下和往右走） 3、初始化：起点 dp[1][0] = 1 或者 dp[0][1] = 1 ，在打表中让第一行和第一列都为0 4、返回值：dp[m][n] 注：在上面多加一行，右边多加一列，防止越界
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
dp[1][0] = 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][n];
}
};2. 不同路径II
题目描述：一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。
思路： 1、状态表示：dp[i][j] 表示：走到[i, j]位置，一共有多少种方法 2、状态转移方程：
- dp[i][j] = dp[i - 1][j] + dp[i][j - 1];（无障碍物）
3、初始化：起点dp[1][0] = 1 或者 dp[0][1] = 1 4、返回值：dp[m][n] 注：在上面多加一行，右边多加一列，防止越界
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& ob) {
int m = ob.size(), n = ob[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
dp[1][0] = 1;
for (int i = 1; i <= m; i++){
for (int j = 1; j <= n; j++){
if(ob[i - 1][j - 1] == 0)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
};3. 珠宝的最高价值
题目描述：现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：
- 只能从架子的左上角开始拿珠宝
- 每次可以移动到右侧或下侧的相邻位置
- 到达珠宝架子的右下角时，停止拿取
注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。
思路： 1、状态表示 dp[i][j] 表示：到[i, j]位置时礼物的最大价值 2、状态转移方程 dp[ i ][ j ] = max(dp[ i - 1 ][ j ] ，dp[ i ][ j - 1] ）+ w[ i ][ j ] (w[i][j] 表示当前位置映射在珠宝架的价值) 3、初始化 我们应该初始化第一行第一列的值，但是我们可以选择多加第一行第一列，把其初始化为0
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame) {
int m = frame.size(), n = frame[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
}
}
return dp[m][n];
}
};4. 最小下降路径
题目描述：给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
思路： 1、状态表示 dp[i][j] 表示：到[i, j]位置 最小下降路径 2、状态转移方程
- 假设 a 表示 dp[i - 1][j -1]，b表示 dp[i - 1][ j]，c表示dp[i - 1][ j + 1]
dp[ i ][ j ] = min(a，b，c ）+ w[ i ][ j ] (w[i][j] 表示当前当前位置映射在珠宝架的价值) 3、初始化 最左边加一列，最右边加一列，最上面加一行
- 里面的值要保证后面填表正确，故最上面那行值为0，左右新增列为 INT_MAX
- 下标映射关系
4、填表顺序：从上往下每一行，每一行从左往右 5、返回值：dp[m][n]
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
// 初始化
vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
for (int j = 0; j < n + 2; j++) dp[0][j] = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) {
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
}
}
int mini = INT_MAX;
for (int j = 1; j <= n; j++) mini = min(dp[n][j], mini);
return mini;
}
};5. 最小路径和
题目描述：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
思路： 1、状态表示 dp[i][j] 表示：到[i, j]位置 最小路径和 2、状态转移方程
- dp[ i ][ j ] = max(dp[ i - 1 ][ j ] ，dp[ i ][ j - 1] ）+ g[ i ][ j ] (g[i][j] 表示当前位置映射在网格数字)
3、初始化 最左边加一列，最上面加一行
- 里面值要保证后面填表正确，故只有[1, 0] 和 [0, 1]位置为0，其他新增均为 INT_MAX
- 下标映射关系
4、填表顺序：从上往下每一行，每一行从左往右 5、返回值：最下面一行的最小值
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[0][1] = dp[1][0] = 0;
for (int i = 1; i <= m; i++){
for (int j = 1; j <= n; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
}
}
return dp[m][n];
}
};6. 地下城游戏
题目描述：恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
思路： 1、状态表示 dp[i][j] 表示：从[i, j]位置出发，到达终点，所需最低初始健康点数 2、状态转移方程
- 往右走，dp[ i ][ j ] = dp[ i ][ j + 1] - d[ i ][ j ]
- 往下走，dp[ i ][ j ] = dp[ i + 1][ j ] - d[ i ][ j ]
- 故dp[ i ][ j ] = min(dp[ i ][ j + 1]，dp[ i + 1][ j ]) - d[ i ][ j ]
- 注：当dp[ i ][ j ] 为负数时就走不了，故dp[ i ][ j ] = max(1，dp[ i ][ j ])
3、初始化 最右边加一列，最下面加一行
- 里面值要保证后面填表正确，因为要保证走到终点救完公主之后肯定有血，故在[m, n - 1] 和 [m - 1, n]血量至少为1，其他新增均为 INT_MAX
- 下标映射关系
4、填表顺序：从下往上每一行，每一行从右往左 5、返回值：dp[0][0]
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& d) {
int m = d.size(), n = d[0].size();
// 1. 创建dp表 + 初始化
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[m][n - 1] = dp[m - 1][n] = 1;
// 2. 填表
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - d[i][j];
dp[i][j] = max(1, dp[i][j]); //避免为负数，因为可以到达下一个点，故在该点至少有一滴血量
}
}
// 3. 返回值
return dp[0][0];
}
};7. 字母收集
思路： 1、预处理 对输入的字符矩阵我们按照要求将其转换为数字分数，由于只能往下和往右走，因此走到（i，j）的位置要就是从（i - 1， j）往下走，或者是从(i，j - 1)的位置往右走，由于我们要使得路程遍历积分最多，则应该从积分多的位置过来， 2、状态表示 dp[i][j] 表示：从[0, 0]出发，到底[i, j]位置，一共有多少分 3、状态转移方程 故（i，j）位置的积分应该为dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i ][ j - 1 ]) + dp[ i ][ j ]; 4、初始化 但是上面仅对于（i >= 1 && j >= 1）成立，对于第一行和第一列我们应该特殊处理，利用前缀和的知识可以求得，走到第一列的第i个位置最多能拿的积分以及走到第一行的第j个位置最多能拿的积分，然后我们就可以按照dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i ][ j - 1 ]) + dp[ i ][ j ]的方法遍历每个节点即可
#include <iostream>
using namespace std;
const int N = 1005;
int dp[N][N];
int main() {
int n, m;
cin >> n >> m;
char ch;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> ch;
if (ch == 'l') dp[i][j] = 4;
else if (ch == 'o') dp[i][j] = 3;
else if (ch == 'v') dp[i][j] = 2;
else if (ch == 'e') dp[i][j] = 1;
else a[i][j] = 0;
}
}
for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + dp[i][0];
for (int j = 1; j < m; j++) dp[0][j] = dp[0][j - 1] + dp[0][j];
for (int i = 1; i < n; i++){
for (int j = 1; j < m; j++){
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + dp[i][j];
}
}
cout << dp[n - 1][m - 1] << endl;
return 0;
}8. 过河卒
图解：
思路： 1、状态表示 dp[i][j] 表示：从[0, 0]出发，到底[i, j]位置，一共有多少种方法 2、状态转移方程 dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[i][j - 1] (i > 0 && j > 0) 当走到马可以走的地方，dp[ i ][ j ] = 0; 3、初始化 先创建一个 dp[ n + 2 ][ m + 2 ]，然后让dp[ 0 ][ 1 ] = 1 或者 dp[ 1 ][ 0 ] = 1。注意这样初始化的时候，x需要+1,y也需要+1.和dp表位置一一对应
#include <iostream>
#include <vector>
using namespace std;
//int dp[1005][1005];
int main()
{
int n, m, x, y;
cin >> n >> m >> x >> y;
vector<vector<long long>> dp(n + 2, vector<long long>(m + 2));
dp[0][1] = 1;
x += 1, y += 1;和dp表位置一一对应
for (int i = 1; i <= n + 1; i++)
{
for (int j = 1; j <= m + 1; j++) { //马所在位置
if (i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x && j == y))
{
dp[i][j] == 0;
}
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
cout << dp[n + 1][m + 1] << endl;
return 0;
}三、子序列和连续序列类
1. mari和shiny
🌈线性 dp 在维护 i 位置之前，⼀共有多少个 "s" "sh" ，然后更新 "shy" 的个数。 （1）状态表示
- s[i]：字符串 str 中 [0, i] 区间内有多少个 "s"。
- h[i]：字符串 str 中 [0, i] 区间内有多少个 "sh"。
- y[i]：字符串 str 中 [0, i] 区间内有多少个 "shy。
（2）状态转移方程
（3）空间优化 用三个变量来表示即可 s：（字符串 str 中 [0, n-1] 区间内有多少个 "s"） h：（字符串 str 中 [0, n-1] 区间内有多少个 "sh"） y：（字符串 str 中 [0, n-1] 区间内有多少个 "shy"） 最后的遍历结束后，y即我们需要的结果
AC代码如下：
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int main()
{
int n;
string str;
cin >> n >> str;
ll s = 0, h = 0, y = 0;
for (int i = 0; i < n; i++) {
if (str[i] == 's') s++;
else if (str[i] == 'h') h += s;
else if (str[i] == 'y') y += h;
}
cout << y << endl;
return 0;
}🌈二维 dp 这道题目如果不是子序列，而是要求连续序列的，那就可以考虑用 KMP。 （1）dp[i][j] 含义
- string t="shy"
dp[i][j]：以 i-1 为结尾的 str 子序列中出现以 j-1 为结尾的 t 的个数为 dp[i][j]。
（2）递推关系
- str[i - 1] 与 t[j - 1]相等
- str[i - 1] 与 t[j - 1] 不相等
当 str[i - 1] 与 t[j - 1]相等时，dp[i][j] 可以有两部分组成：
- 一部分是用 str[i - 1] 来匹配，那么个数为 dp[i - 1][j - 1]。即不需要考虑当前 str 子串和 t 子串的最后一位字母，所以只需要 dp[i-1][j-1]。
- 一部分是不用 str[i - 1] 来匹配，个数为 dp[i - 1][j]。
为什么还要考虑不用 str[i - 1] 来匹配，都相同了指定要匹配？ 🧩例如： str：shyy 和 t：shy ，str[3] 和 t[2] 是相同的，但是字符串 str 也可以不用 str[3] 来匹配，即用 str[0]str[1]str[2] 组成的 "shy"。当然也可以用 str[3] 来匹配，即：str[0]str[1]str[3] 组成的 "shy"。 所以，当 str[i - 1] 与 t[j - 1] 相等时，dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + dp[ i - 1 ][ j ]; 当 str[i - 1] 与 t[j - 1] 不相等时，dp[i][j] 只有一部分组成，不用 str[i - 1] 来匹配（就是模拟在 str 中删除这个元素），即：dp[i - 1][j]，所以递推公式为：dp[ i ][ j ] = dp[ i - 1 ][ j ]; 为什么只考虑 “不用 str[i - 1] 来匹配” 这种情况， 不考虑 “不用 t[j - 1] 来匹配” 的情况呢？ 🧩这里要明确，我们求的是 str 中有多少个 t，而不是求 t 中有多少个 str，所以只考虑 str 中删除元素的情况，即不用 str[i - 1] 来匹配 的情况。
（3）状态转移方程
- dp[i][j]显然要从dp[i-1][?]递推而来。立即思考dp[i-1][j], dp[i-1][j-1]分别与dp[i][j]的关系。因为少一个字符，自然而然从当前字符着手。考察si的第i个字符(表为s[i])和tj的第j个字符(表为t[j])的关系。
- 若s[i] ≠ t[j]：那么s_i中的所有t_j子序列，必不包含s[i]，即s_i-1和s_i中tj的数量是一样的，得到该情形的转移方程： dp[ i ][ j ] = dp[ i -1 ][ j ]
- 若s[i] = t[j]：假设s_i中的所有t_j子序列中，包含s[i]的有a个，不包含的有b个。s_i中包含s[i]的子序列个数相当于s_i-1中t_j-1的个数，不包含s[i]的子序列个数与上一种情况一样，于是得到该情形的转移方程： a = dp[ i -1 ][ j -1 ] b = dp[ i-1 ][ j ] dp[ i ][ j ] = a + b = dp[i-1][j-1] + dp[i-1][j]
（4）遍历顺序 从上到下，从左到右。
AC代码如下：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
string str;
cin >> str;
string t="shy";
int m=t.size();
vector<vector<long long>> dp(n+1, vector<long long>(m+1));
for(int i=0; i<=n; i++) dp[i][0]=1;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(str[i-1]==t[j-1])
dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
else
dp[i][j]=dp[i-1][j];
}
}
cout << dp[n][m] << endl;
return 0;
}2. 不同的子序列
该题于上题不一样的是，上面给定了t的具体字符串，而这里没有给定，但是我们也需要用二维dp的方法来写。 （1）dp[i][j] 含义 s[ i ]的子序列中在t[ j ]出现的次数 s[ i ]表示s从下标 i 到末尾的子字符串。 t[ j ]表示t从下标 j 到末尾的子字符串。
（2）递推关系
- 分别令两个维度为0，推测边界。
- dp[0][j]表示s_0中t_j的个数。s_0是空字符串，只有当j=0时，才有dp[0][j] = 1，表示s子空串中有一个t子空串，否则dp[0][j] = 0，因为一个空串不可能包含一个非空串。
- dp[i][0]表示s_i中t0的个数。t_0是空字符串，显然任何串（包括空串）都含有一个空子串。因此dp[i][0] = 1。
- 注意到，dp[i][0] = 1实际上已经包含了dp[0][j] = 1的情形。
（3）初始化
- dp[i][0] 表示：以 i-1 为结尾的 str 可以随便删除元素，出现空字符串的个数。所以，dp[i][0] 一定都是 1，因为也就是把以 i-1 为结尾的 str，删除所有元素，出现空字符串的个数就是 1。
- dp[0][j] 表示：空字符串 str 可以随便删除元素，出现以 j-1 为结尾的字符串 t 的个数。所以，dp[0][j] 一定都是 0，因为 str 如论如何也变成不了 t。
- dp[0][0] 表示：空字符串 str 可以删除 0 个元素，变成空字符串 t。所以，dp[0][0] = 1。
（4）遍历顺序 从上到下，从左到右。
AC代码如下：
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
if (n < m) return 0;
vector<vector<unsigned int>> dp(n + 1, vector<unsigned int>(m + 1)); //注意是unsigned int
for (int i = 0; i <= n; i++) dp[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j] +(s[i - 1] == t[j - 1] ? dp[i - 1][j - 1] : 0);
}
}
return dp[n][m];
}
3. 连续子数组最大和
思路： 1、状态表示 dp[ i ]表示：以 i 位置为结尾的所有子数组中的最大和 方法一： 2、状态转移方程 对于nums[i]有两种情况:一种是和前一个位置的子序列连着dp[i]=dp[i-1]+nums[i] 第二种是以自己独立门户，从自己开始dp[i]=nums[i] 取其中最大值,可得状态转移方程为 dp[ i ] = max(dp[i - 1] + nums[i], nums[i]) ; 3、初始化 dp[0]=nums[0] 方法二： 2、状态转移方程 dp[ i ] = max(dp[ i - 1 ] ， 0） + nums[ i - 1 ] . 3、初始化 dp[ 0 ] = 0，然后从下标1开始计算，最后返回 dp 表的最大值即可
AC代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> dp(n + 1);
int w, ret = -101;
for (int i = 1; i <= n; i++) {
cin >> w;
dp[i] = max(dp[i - 1], 0) + w;
ret = max(ret, dp[i]);
}
cout << ret << endl;
return 0;
}4. 最长回文子序列
思路： 1、状态表示 dp[ i ][ j ] 表示：字符串[ i，j] 区间内最长回文子序列的长度 2、状态转移方程
- i > j 时，dp[ i ][ j ] = 0;
- i = j 时，dp[ i ][ j ] = 1;
- i < j，分以下两种情况
- s[ i ] = s[ j ]时候，dp[ i + 1][ j - 1] +2;
- s[ i ] != s[ j ]时候，max(dp[i - 1][ j ]，dp[ i ][ j - 1] )
3、初始化 dp[ 0 ] = 0，然后从下标1开始计算，最后返回 dp 表的最大值即可
AC代码如下：
int longestPalindromeSubSeq(string s) {
// write code here
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
//i为起始索引，j为结束索引
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
//相同，则加2
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
//不同，则从dp[i+1][j] dp[i][j-1]中寻找最大值。
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}四、偷盗问题 💢
1. 打家劫舍 I
题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
思路： 首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？ 方法一：二维 1、状态表示 设 dp[i][0] 为不偷第 i 个房间的情况下，前 i 个数偷盗总金额的最大值；dp[i][1]为取第 i 个数的情况下，前 i 个数不偷盗总金额的最大值。 2、状态转移方程 不偷当前房间，那么前一个房间取不取都行： dp[i][0]=max(dp[i−1][1],dp[i−1][0]) 若取当前房间，那么前一个房间一定不能取： dp[i][1]=dp[i−1][0]+ nums[i - 1] 最后需要输出 max(dp[n][0],dp[n][1]) 方法二：一维 对于 k（ k > 2）的房屋数量，有两个选项：
- 偷窃第k间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
- 不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。 在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。
1、状态表示 dp[ i ]：表示前 i + 1间房屋能偷盗的最多钱数。(下标从0开始) 2、状态转移方程 dp[ i ] = max(dp[ i - 2 ] + nums[ i ] , dp[i - 1] ) 提示里说了nums.length>=1; 对于nums.length==1，需特殊处理，return nums[0];
AC代码如下：
int rob(vector<int>& nums) {
int n = nums.size();
// 方法一：二维表示
/*vector<vector<int>> dp(n + 1, vector<int>(n + 1));
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 - 1];
}
return max(dp[n][0], dp[n][1]);*/
//方法二：一维表示
if (n == 1) return nums[0];
vector<int> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; ++i) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1] );
}
return dp[n - 1];
//方法三：再优化
int f1 = 0, f0 = 0;
for (int i = 0; i < n; i++) {
int tmp = max(f1, f0 + nums[i]);
f0 = f1;
f1 = tmp;
}
return f1;
}2. 打家劫舍 II
思路： 这道题中的房屋是首尾相连的，第一间房屋和最后一间房屋相邻，因此第一间房屋和最后一间房屋不能在同一晚上偷窃。通过分类讨论，将环形问题转化为两个线性的打家劫舍 I 考虑是否偷 nums[0]：
- 如果偷 nums[0]，那么 nums[1] 和 nums[n−1] 不能偷，问题变成从 nums[2] 到 nums[n−2] 的非环形版本。
- 如果不偷 nums[0]，那么问题变成从 nums[1] 到 nums[n−1] 的非环形版本。
- 分别取 [start,end)=[2,n−2) 和 [start,end)=[1,n−1) 进行计算，取两个 dp[end] 中的最大值，即可得到最终结果
假设偷窃房屋的下标范围是 [start,end]，用 dp[i] 表示在下标范围 [start,i] 内可以偷窃到的最高总金额： 1、状态表示 dp[ i ]：表示前 i 间房屋能偷盗的最多钱数。 2、状态转移方程 dp[i]=max(dp[i−2]+nums[i],dp[i−1]) 注意：这题我们用 tmp, f1, f0 来分别表示dp[i]，dp[i - 1]，dp[i -2]。
AC代码如下：
class Solution {
public:
int robRange(vector<int>& nums, int l, int r) { // 总共有 r - l + 1间房
if (l > r) return 0;
if (l == r) return nums[l];
vector<int> dp(r + 1);
dp[l] = nums[l];
dp[l + 1] = max(nums[l], nums[l + 1]);
for (int i = l + 2; i < r + 1; ++i) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[r]; // 这里r就相当于打家劫舍I中的n - 1
}
int rob(vector<int>& nums) {
int n = nums.size();
return max(nums[0] + robRange(nums, 2, n - 2), robRange(nums, 1, n - 1));
}
};3. 打家劫舍 III
思路： 对于当前节点，就两个选择，抢或者放弃。然后我们用 f(o) 表示抢 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和；g(o) 表示不抢 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和；l 和 r 代表 o 的左右孩子。 🧩1、当 o 被选中时，o 的左右孩子都不能被选中，故 o 被选中情况下子树上被选中点的最大权值和为 l 和 r 不被选中的最大权值和相加，即 f(o)=g(l)+g(r)。 🧩2、当 o 不被选中时，o 的左右孩子可以被选中，也可以不被选中。对于 o 的某个具体的孩子 x，它对 o 的贡献是 x 被选中和不被选中情况下权值和的较大值。故 g(o)=max{f(l),g(l)}+max{f(r),g(r)}。 🧩至此，我们可以用哈希表来存 f 和 g 的函数值，用深度优先搜索的办法后序遍历这棵二叉树，我们就可以得到每一个节点的 f 和 g。根节点的 f 和 g 的最大值就是我们要找的答案。
AC代码如下：
unordered_map<TreeNode*, int>f, g;
void dfs(TreeNode* node)
{
if (node == nullptr) return;
dfs(node->left), dfs(node->right);
f[node] = node->val + g[node->left] + g[node->right]; //如果抢该节点
g[node] = max(f[node->left], g[node->left])
+ max(f[node->right], g[node->right]);
}
int rob(TreeNode* root) {
dfs(root);
return max(f[root], g[root]);
}4. 打家劫舍 IV
思路： 通过观察可以发现，当偷盗能力越大时，小偷最多能偷的房屋数就越多；如果偷盗能力越小时，小偷最多能偷的房屋数就越少。 由题意我们可知，这是求最小的最大值，因此我们可以想到用二分的方法来找到合适的 capacity。对于每个通过二分列举出来的 capacity，因为碍于偷盗能力，小偷只能偷价值不超过 capacity 的房子，而且不能连续偷。因此，我们可以通过动态规划的方法算出：当小偷的偷盗能力为 capacity 时，小偷可以最多可以偷多少间房（设为 y），如果 y >= k，那么就代表 capacity 偏大，要把 capacity 调小一点；如果 y < k，那么就代表 capacity 偏小，把 capacity 调大一点。且由于要求的是最小的最大值，因此属于二分里面的区间左端点问题。 处。 通过二分枚举 capacity，对每个 capacity 进行动态规划，求出在该 capacity 的情况下最多偷到的房屋数，然后再根据这个房屋数调整 capacity 的查找区间。
AC代码如下：
int minCapability(vector<int>& nums, int k) {
vector<int> capacity = nums;
sort(capacity.begin(), capacity.end());
int l = 0, r = capacity.size() - 1;
while (l < r)
{
int m = (r - l >> 1) + l; //注意：+， -的优先级高于>>
if (check(nums, capacity[m]) >= k)r = m;
else l = m + 1;
}
return capacity[l];
}
int check(vector<int>& nums, int capacity)
{
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(2));
for (int i = 1; i <= n; i++)
{
if (nums[i - 1] <= capacity) dp[i][1] = dp[i - 1][0] + 1;
dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
}
return max(dp[n][1], dp[n][0]);
}5. 删除并获得点数
题目描述：给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数
思路： 用arr数组来表示：数字 i 在nums数组出现的总和，此时问题就转化为在arr数组中做一次打家劫舍II即可
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
const int N = 10001;
// 1. 预处理
int arr[N] = { 0 };
for (auto x : nums) arr[x] += x;
// 2. 在arr数组上进行打家劫舍问题
vector<int> dp(N);
dp[0] = arr[0];
dp[1] = max(arr[1], arr[0]);
for (int i = 2; i < N; i++) {
dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);
}
return dp[N - 1];
}
};6. 粉刷房子
题目描述：假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
思路： 1、状态表示
- dp[ i ][ 0 ] 表示：粉刷到 i 位置时，最后一个位置粉刷上红色的最小花费
- dp[ i ][ 1 ] 表示：粉刷到 i 位置时，最后一个位置粉刷上蓝色的最小花费
- dp[ i ][ 2 ] 表示：粉刷到 i 位置时，最后一个位置粉刷上绿色的最小花费
2、状态转移方程 假设第 i 个位置涂红色，那么此时增加花费为costs[ i ][ 0 ]，要使花费最小，则前 i - 1个位置花费最小，则对于 i - 1位置有两种颜色可涂，故我们可以得到
- dp[ i ][ 0 ] = min(dp[ i - 1 ][ 1 ] ，dp[ i - 1 ][ 2 ] ）+ costs[ i ][ 0 ]
- dp[ i ][ 1 ] = min(dp[ i - 1 ][ 0 ] ，dp[ i - 1 ][ 2 ] ）+ costs[ i ][ 1 ]
- dp[ i ][ 2 ] = min(dp[ i - 1 ][ 0 ] ，dp[ i - 1 ][ 1 ] ）+ costs[ i ][ 2 ]
3、初始化 要避免填表初始化越界，故我们可以在最前面新增一个节点
- 新增点里面值要保证后面填表正确，因此值为0
- 下标映射关系
4、填表顺序：从左往右填表，一次同时填写三个 5、返回值：min(dp[n][0]，dp[n][1]，dp[n][2])
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
// 1. 创建 dp 表
vector<vector<int>> dp(n + 1, vector<int>(3));
for (int i = 1; i <= n; i++)
{
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
}
return min(dp[n][0], min(dp[n][1], dp[n][2]));
}
};五、买卖股票🎫
1. 买卖股票的最好时机 I
题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
思路： 以某个点为卖出点，然后以其前面的最小点为买入点，然后不断往后走即可。
class Solution {
public:
int maxProfit(vector<int>& prices) {
//在前i天内， premin 表示的最小卖出，ans 表示最大利润
int premin = prices[0], ans = 0;
for (int i = 0; i < prices.size(); i++){
ans = max(ans, prices[i] - premin);
premin = min(premin, prices[i]);
}
return ans;
}
};2. 买卖股票的最佳时机 II
题目描述：给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
思路： 该题与上题思路相同，当该天卖出大于上一天买入时，就把该股票卖出即可，返回利润总和即可
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ret = 0;
for (int i = 1; i < prices.size(); i++){
if (prices[i] > prices[i - 1]) ret += prices[i] - prices[i - 1];
}
return ret;
}
};3. 买卖股票的最佳时机含冷冻期
题目描述：给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路： 1、状态表示
- dp[ i ][ 0 ] 表示：第 i 天结束后，处于 “买入状态” 的最大利润
- dp[ i ][ 1 ] 表示：第 i 天结束后，处于 “可交易状态” 的最大利润
- dp[ i ][ 2 ] 表示：第 i 天结束后，处于 “冷冻期状态” 的最大利润
2、状态转移方程 假设第 i 天处于买入状态则对于第 i - 1天可以处于买入状态，那么下一天就啥也不做， 第 i - 1天处于可交易状态，那么 - price[ i ]就可进入 买入状态， 再或者第 i 天处于买入状态，那么 + price[ i ]就可进入 冷冻期状态
- dp[ i ][ 0 ] = max(dp[ i - 1 ][ 0 ] ，dp[ i - 1 ][ 1 ] - prices[ i ] )【当天结束处于买入】
- dp[ i ][ 1 ] = max(dp[ i - 1 ][ 1 ] ，dp[ i - 1 ][ 2 ] ）【当天结束处于可交易】
- dp[ i ][ 2 ] = dp[ i - 1 ][ 0 ] + prices[ i ]【当天结束处冷冻期】
3、初始化
- dp[ 0 ][ 0 ]：表示第0天处于买入，那么只能买入股票，最大利润肯定为 -prices[0]
4、填表顺序：从左往右填表，一次填写三个 5、返回值：max(dp[n - 1][1]，dp[n - 1][2])
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(3));
dp[0][0] = -prices[0];
for (int i = 1; i < n; i++)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
dp[i][2] = dp[i - 1][0] + prices[i];
}
return max(dp[n - 1][1], dp[n - 1][2]);
}
};4. 买卖股票的最佳时机含手续费
题目描述：给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
思路： 1、状态表示 f [ i ] 表示：第 i 天结束之后，处于买入状态的最大利润 g[ i ] 表示：第 i 天结束之后，处于卖出状态的最大利润 2、状态转移方程
- f[ i ] = max(f[ i - 1 ]，g[ i - 1 ] - prices[ i ]);
- g[i] = max(g[ i - 1 ], f[ i - 1 ] + prices[ i ] - fee);
3、初始化
- 在第0天处于买入状态，f[0] = - prices[0]，g[0] = 0.
4、填表顺序：从左往右填表 5、返回值：g[n - 1]（因为 在最后一天，买入状态一定手持股票，处于卖出肯定比买入状态利润大）
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<int> f(n), g(n);
f[0] = -prices[0], g[0] = 0;
for (int i = 1; i < n; i++)
{
f[i] = max(f[i - 1], g[i - 1] - prices[i]);
g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
}
return g[n - 1];
}
};5. 买卖股票的最佳时机III
题目描述：假设你有一个数组，其中第i个元素是某只股票在第i天的价格。 设计一个算法来求最大的利润。你最多可以进行两次交易。但是你不能同时进行多个交易(即必须在再次购买之前出售之前买的股票)。
思路： 1、状态表示 f [ i ][ j ] 表示：第 i 天结束之后，完成了 j 次交易，处于买入状态的最大利润 g[ i ][ j ] 表示：第 i 天结束之后，完成了 j 次交易，处于卖出状态的最大利润 2、状态转移方程
- f[ i ][ j ] = max(f[ i - 1 ][ j ]，g[ i - 1 ][ j ] - prices[ i ]);
- g[ i ][ j ] = max(g[ i - 1 ][ j ]，f[ i - 1 ][ j - 1 ] + prices[ i ]); (逗号右边条件仅限于 j >= 1，才可以)
3、初始化 由于在第0天处于买入状态，最多买入一次
- f [ 0 ][ 0 ] = - prices[0]，f [ 0 ][ 1 ] = INT_MIN，f [ 0 ][ 2 ] = INT_MIN
- g[ 0 ][ 0 ] = - prices[0]，g[ 0 ][ 1 ] = INT_MIN，g[ 0 ][ 2 ] = INT_MIN
- 注：这里最小值应该选 0x3f3f3f3f，避免越界
4、填表顺序：从上往下填表，每一行从左往右，两个表一起填 5、返回值：max(g[n - 1][ j ]) （其最后一行的最大值）
class Solution {
public:
const int INF = 0x3f3f3f3f;
int maxProfit(vector<int>& prices) {
int n = prices.size();
// 1. 创建 dp 表
vector<vector<int>> f(n, vector<int>(3,-INF)); // n 天最多完成 2 笔交易
auto g = f;
// 2. 初始化
f[0][0] = -prices[0], g[0][0] = 0;
// 3. 填表
for (int i = 1; i < n; i++)
{
for (int j = 0; j < 3; j++)
{
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
g[i][j] = g[i - 1][j];
if(j >= 1)g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
}
}
// 4. 返回值
int maxi = 0;
for (int j = 0; j < 3; j++) maxi = max(maxi, g[n - 1][j]);
return maxi;
}
};6. 买卖股票的最佳时机IV
题目描述：给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路： 该题与上题类似，我们定义两个 n行 k 列的二维dp表，来表示 n 天最多完成 k 笔交易 注：k无论多大，在 n 天内最多进行 n / 2 次交易，因此我们应该对k 进行优化。
class Solution {
public:
const int INF = -0x3f3f3f3f;
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
k = min(k, n / 2); // 细节处理
vector<vector<int>> f(n, vector<int>(k + 1, INF));
auto g = f;
f[0][0] = -prices[0], g[0][0] = 0;
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= k; j++)
{
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
g[i][j] = g[i - 1][j];
if (j >= 1)g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
}
}
// 4. 返回值
int maxi = 0;
for (int j = 0; j <= k; j++) maxi = max(maxi, g[n - 1][j]);
return maxi;
}
};六、背包问题🎒
1. 01背包问题
1、状态表示 dp[ i ][ j ]表示：从前 i 个物品中挑选，总体积不超过j，此时最大的重量 2、状态转移方程 dp[ i ][ j ] = max (dp[i - ][ j ] (不选i)， dp[i - 1][ j - v[ i ]] + w[ i ] (选i) ) 3、初始化问题 dp[ 0 ][ j ] = 0 ; 4、 返回dp[n][V]. 5、空间优化 dp[ j ] = max ( dp [ j ], dp[ j - v[ i ] + w [ i ] ]
AC代码如下：
#include <iostream>
using namespace std;
const int N = 1005;
int dp[N], v[N], w[N];
int main() {
int n, V;
cin >> n >> V;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; //体积权重
for (int i = 1; i <= n; i++) { //体积
for (int j = V; j >= v[i]; j--) { //逆序，表示该物品最多使用一次
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V] << endl;
return 0;
}2. 完全背包问题
思路： 和上题不同的是，01背包中n件物品只能使用一次，而这里可以无限次使用 那么我们可以把这题把多次使用的某件物品看作多次插入，那么这道题的解题步骤就和上面类似了，状态转移方程也基本和上面类似，我们这里同样也进行了空间优化。 上一篇代码中，我们用的是逆序是为了保证更新当前状态时，用到的状态是上一轮的状态，保证每个物品只有一次或零次; 在这里，因为每个物品可以取任意多次，所以不再强求用上一轮的状态，即本轮放过的物品，在后面还可以再放;
AC代码如下：
#include <iostream>
using namespace std;
const int N = 1010;
int dp[N],v[N], w[N];
int main(){
int n, V;
cin >> n >> V;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++){
for (int j = v[i]; j <= V; j++){
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V] << endl;
return 0;
}3. [NOIP2001]装箱问题
思路： 该题也是个典型的01背包问题 1、状态表示 dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j，此时的最大体积 2、状态转移方程 dp[ i ][ j ] = max(dp[ i - 1 ][ j ] ，dp[ i ][ j - V[ i ]] + V[ i ]) （j >= arr[ i ]） 3、初始化 返回 V - dp[ n ][ V ]
AC代码如下：
const int N = 35, M = 2e4 + 10;
int v[N], dp[N][M];
void solve3(){
int V, n;
cin >> V >> n;
for (int i = 1; i <= n; i++) cin >> v[i];
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < V; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= v[i])
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + v[i]);
}
}
cout << V - dp[n][V] << endl;
}4. 分割等和子集
思路： 该题也是个典型的01背包问题 1、状态表示 dp[i][j] 表示：从前 i 个数字中挑选，总和恰好为 j，看是否能够凑成，因此我们这的dp数组为bool类型 2、状态转移方程 第一种：最后一个数不选，先从前i - 1个数中挑，因为最后一个不选，对总和不造成影响， 如果我们从前 i - 1种情况能凑成j，那么在从前 i种情况肯定能凑成j 第二种：选了第i个数字，那从前i - 1个数中挑，对总和会造成影响，因此我们应该在前i - 1个数中凑总和为 j - arr[ i ]即可 dp[ i ][ j ] = dp[ i - 1 ][ j ] || dp[ i ][ j - arr[ i ]] （j >= arr[ i ]） 3、初始化 在之前的dp表基础上多加一行多加一列，方便我们初始化，初始dp[0][0] = true. 4、返回值 返回dp[ n ][ sum / 2] 即可 注：如果总和为奇数，永远都选不出来一半，直接返回false即可。
AC代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 505, M = 505 * 110 / 2;
bool dp[N][M];
int arr[N];
int main()
{
int n;
cin >> n;
int sum = 0;
// 1.计算总和
for (int i = 1; i <= n; i++) {
cin >> arr[i];
sum += arr[i];
}
// 2.判断总和是否为奇数，为奇数直接截止
if (sum % 2 == 1) {
cout << "false" << endl;
return 0;
}
// 3.动态规划
sum /= 2;
dp[0][0] = true; //初始化
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= sum; j++) {
dp[i][j] = dp[i - 1][j]; //当i = 0，j = 0的初始化
if(j >= arr[i])
dp[i][j] = dp[i - 1][j] || dp[i][j - arr[i]];
}
}
if (dp[n][sum]) cout << "true" << endl;
else cout << "false" << endl;
return 0;
}七、树形DP
1. 二叉树中的最大路径和
思路： 我们需要返回经过每个根节点的最大路径和，这题主要是递归/树形DP ret = max(root->val + l + r, ret) 左子树提供：以左子树为根的最大单链和：l = max(0，l) 右子树提供：以右子树为根的最大单链和：r = max(0，r) 返回值：以我为根的最大单链和：root->val + max(l ,r )
int ret = -1010;
int dfs(TreeNode* root){
if (root == nullptr) return 0;
//注：如果为负数时就不过该节点了
int l = max(0,dfs(root->left)); //左子树为根的最大单链和
int r = max(0,dfs(root->right)); //右子树为根的最大单链和
// 经过 root 的最大路径和
ret = max(ret, root->val + l + r);
return root->val + max(l, r);
}
int maxPathSum(TreeNode* root) {
// write code here
dfs(root);
return ret;
}腾讯云开发者
