文章目录
- 引子：凑零钱
- 一、斐波那契数列模型
-
- 引例：第 N 个泰波那契数
-
- 动态规划步骤
- 空间优化
- 例题1 三步问题
- 例题2：使用最小花费爬楼梯★
- 例题3：解码方法 ★
- 二、路径问题
-
- 例题4：不同路径
- 例题5：下降路径最小和
- 例题6：地下城游戏 ★
- 三、简单多状态 dp 问题
-
- 例题7：按摩师 ★
- 例题8：打家劫舍 II
- 例题9：删除并获得点数
- 例题10：粉刷房子
- 例题11：买卖股票的最佳时机含冷冻期 ★
- 例题12：买卖股票的最佳时机 III ★
- 例题13：买卖股票的最佳时机 IV
- 四、子数组、子串系列
-
- 例题14：最大子数组和 ★
- 例题15：环形子数组的最大和
- 例题16：乘积最大子数组
- 例题17：乘积为正数的最长子数组长度
- 例题18：等差数列划分
- 例题19：最长湍流子数组 ★
- 例题20：单词拆分 ★
- 例题21：环绕字符串中唯一的子字符串
- 五、子序列问题
-
- 例题22：最长递增子序列
- 例题23：摆动序列
- 例题24：最长递增子序列的个数 ★
- 例题25：最长数对链
- 例题26：最长定差子序列 ★
- 例题27：最长的斐波那契子序列的长度 ★
- 例题28：最长等差数列 ★
- 例题29：等差数列划分 II – 子序列
- 六、回文串问题
-
- 例题30：回文子串 ★
- 例题31：最长回文子串
- 例题32：分割回文串 II
- 例题33：最长回文子序列 ★
- 例题34：让字符串成为回文串的最少插入次数 ★
- 七、两个数组的 dp
-
- 例题35：最长公共子序列 ★
- 例题36：不相交的线
- 例题37：不同的子序列 ★
- 例题38：通配符匹配 ★
- 例题39：正则表达式匹配 ★
- 例题40：交错字符串 ★
- 例题41：两个字符串的最小ASCII删除和 ★
- 例题42：最长重复子数组 ★
- 八、01 背包问题
-
- 例题43：【模板】01背包
- 例题44：分割等和子集
- 例题45：目标和 ★
- 例题46：最后一块石头的重量 II ★
- 九、完全背包问题
-
- 例题47：【模板】完全背包 ★
- 例题48：零钱兑换
- 例题49：零钱兑换 II
- 例题50：完全平方数
- 十、二维费用的背包问题
-
- 例题51：一和零 ★
- 例题52：盈利计划
- 十一、似包非包
-
- 例题53：组合总和 Ⅳ
- 十二、卡特兰数
-
- 例题54：不同的二叉搜索树 ★
引子：凑零钱
这部分全是我的碎碎念：本来是在刷蓝桥杯真题的，结果有一道题不会，看别人的题解说用到了什么“状态压缩DP”，不明白，就去DP是什么意思 —— Dynamic Programming（动态规划），于是就去找资料学动态规划，后来发现一个点赞量超高的知乎帖子，看那位大佬写的那么多那么细，以为自己能学懂，不想最开始的问题就给我整不会了（其实现在看来大佬写的确实很清楚，可能是我太笨了，当时就是看不懂 —— 如果你和我一样笨，这篇博客应该能帮到你），这个问题即：凑零钱
知乎大佬的文章：
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
问：你现在手上有面额为 1 5 11 三种纸币，数量不限，如何用最少的纸币凑出 n 元？
示例：输入 15，输出 3（5+5+5）
显然这道题用所谓的贪心算法做不出来（贪心算法思路：每次取当前能使用的最大面额的纸币尽快凑出结果 – 显然对于人民币那 1 5 10 20 50 100 的面额去凑钱，贪心算法就是最优解，但我们这道题就是这么奇葩）
于是就可以用所谓的动态规划解这道题：
//写法和知乎大佬略有不同，但殊途同归
int func(int money) {
int n = money;
vector<int> dp(n+1);//dp[i]：i 块钱最少需要几张
dp[0] = 0; dp[1] = 1;
//dp[i] = max(dp[i-1],dp[i-5],dp[i-11]);
for (int i = 2; i <= n; i++) {
if (i < 5) dp[i] = dp[i - 1] + 1;
else if (i >= 5 && i < 11) dp[i] = min(dp[i - 1], dp[i - 5]) + 1;
else {
dp[i] = min(min(dp[i - 1], dp[i - 5]), dp[i - 11]) + 1;
}
}
return dp[n];
}
看不懂？没关系，我一开始也看不懂，就连这个代码也是我学了一段时间后才写出来的，接下来正式开始动态规划的学习：
一、斐波那契数列模型
引例：第 N 个泰波那契数
第 N 个泰波那契数
显然这道题用递归直接秒了：
class Solution {
public:
void func(int n1,int n2,int n3,int& res, int num){
if(num == 0) return;
res = n1 + n2 + n3;
func(n2,n3,res,res,num - 1);
}
int tribonacci(int n) {
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
int res = 0;
func(0,1,1,res,n - 2);
return res;
}
};
但我们不是来学递归怎么写的，我们要想的是：动态规划是什么？如果用动态规划应该怎么办？
动态规划步骤
- 状态表示
- 状态转移方程
- 初始化
- 填表顺序
- 返回值
第一步：状态表示
我们先创建一个dp表（是一个一维或二维数组）并将其填满，其中的某一个值可能就是我们的最终结果。dp表中其中相应位置的值有特殊的含义，我们称这个为状态表示
感性理解：状态表示是什么？ —— dp表里的值代表的含义
状态表示怎么来的（是如何确定的）？
1.题目要求
2.经验（多做题）+题目要求
3.在分析问题的过程中发现重复子问题（听起来挺抽象，但其实不难，比如引子的解法就是用了这个思路，不过老师建议先把重心放在前两种情况）
4.其他方法
在这个题目中我们创建一个一维的dp表，由题目要求得到 它的状态表示 dp[i] 为第 i 个泰波那契数的值
第二步：状态转移方程
即：dp[i] 等于什么？ 这个问题听起来很抽象，但我们结合题目，这个题目很直观的写出了 dp[i] = dp[i – 1] + dp[i – 2] + dp[i – 3]，这个公式就是状态转移方程
重点就在前两步上
后三步在处理一些细节问题
第三步：初始化
保证填表的时候不越界
显然状态转移方程中的 dp[i] 中的i不能是 0、1、2，所以我们先把他们初始化：dp[0] = 0; dp[1] = 1; dp[2] = 1;
第四步：填表顺序
为什么需要确定填表顺序：我们需做到 填写当前状态时，所需要的状态已经计算过了
eg. 根据本题的方程，我们肯定是dp[3]、dp[4]、dp[5]……挨个填，不能跳过dp[3]去填dp[4]
第五步：返回值
本题返回 dp表的最后一个数
class Solution {
public:
int tribonacci(int n) {
//处理一些边界情况，防越界
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
//创建dp表
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];
}
};
空间优化
直到后面的背包问题之前我们都不会再讲空间优化，因为我们的重心应当先放在掌握动态规划的五个步骤
空间优化一般都用滚动数组的方法
在我们这个题里，dp[i] 仅与它的前三个数据有关，我们创建四个变量a、b、c、d，其中让 a、b、c 就像 是在原来的dp表上向右滚动获取其中的数值一般，d为 a+b+c 的结果，我们可以把a、b、c放进数组中形成滚动数组
代码实现：
class Solution {
public:
int tribonacci(int n) {
//处理一些边界情况，防越界
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
//dp表换成滚动“数组”
int a = 0, b = 1, c = 1, d = 0;
//修改状态转移方程
for(int i = 3; i <= n; i++){
d = a + b + c;
//滚动操作
a = b; b = c; c = d;
}
//修改返回值
return d;
}
};
空间优化的结果（空间复杂度）：
O(n^2) -> O(n)
O(n) -> O(1)
例题1 三步问题
三步问题
不难，直接上题解：
class Solution {
public:
int waysToStep(int n) {
int MOD = 1e9+7;
//处理边界情况
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
//状态表示 dp表
int dp[10000001];
//状态转移方程：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
//逻辑：第i阶台阶怎么上？i-1阶上1步、i-2阶上两步、i-3阶上三步
//——为什么全是一步到位，不考虑像是i-3阶上1步再上2步这些步骤吗——这个已经在i-2中包含了，你猜怎么上的i-2阶？
//初始化
dp[1] = 1; dp[2] = 2; dp[3] = 4;
for(int i = 4;i <= n;i++){
dp[i] = ((dp[i - 1] + dp[i - 2])%MOD + dp[i - 3])%MOD;//因为数很大，需要在这里取模处理一下
//(dp[i - 1] + dp[i - 2])%MOD 在整体取模前还要这样给这两个数取一次模是因为我这个数组的数据类型是int（默认有符号整形），范围为-20亿到20亿（显然我们不想得到负数），虽然数组里的每个数据的大小都被最后的整体取模限制在了MOD（10亿）的范围以内，但如果这里没有取模操作，但凡是三个10亿相加超了20亿，那我们的结果就错了
//综上所述，如果你不想取这个模，你也可以把数组的数据类型换一下：unsigned int dp[10000001]
}
//返回
return dp[n]%MOD;
}
};
例题2：使用最小花费爬楼梯★
使用最小花费爬楼梯
方法一：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//状态表示dp表
int n = cost.size();
vector<int> dp(n+1);//楼梯顶是dp[n]
//状态转移方程：dp[i] = min{dp[i-1] + cost[i-1],dp[i-2]+cost[i-2]}
//dp[i]从出发位置到此处的最低花费
//到达dp[i]所需花费为 到达dp[i-1]所需的花费+从dp[i-1]处爬到dp[i]所需的花费 与 到达dp[i-2]所需的花费+从dp[i-2]处爬到dp[i]所需的花费 两者的最小值
//经过子问题的层层把守（dp[i]依据的数据都已是被比较出的最优解），我就能比较出最低花费，想不明白这种写法和暴力求解（穷举）的区别的话可以试着分析下 1,5,1000,1 的情形
dp[0] = 0; dp[1] = 0;
for(int i = 2;i <= n;i++){//时间复杂度O(N)
dp[i] = min(dp[i-1] + cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
};
方法二：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
const int n = cost.size();
vector<int> dp(n);
//状态转移方程：dp[i] = min{dp[i+1]+cost[i], dp[i+2]+cost[i]}
//我们求从0或1下标位置处到楼顶的最低花费，而dp[i]表示从i位置出发到楼顶的最低花费
//从dp[i]往上爬1层（加上dp[i]位置处的花费），从dp[i+1]位置出发向楼顶
//从dp[i]往上爬2层（加上dp[i]位置处的花费），从dp[i+2]位置出发向楼顶
//初始化
dp[n-1] = cost[n-1]; dp[n-2] = cost[n-2];
for(int i = n-3;i >= 0;i--){
dp[i] = cost[i] + min(dp[i+1], dp[i+2]);
}
return min(dp[0],dp[1]);
}
};
例题3：解码方法 ★
解码方法
状态表示：
根据我们此前的经验和题目要求，前两个问题我们都用dp[i]表示“到位置 i 为止……”，所以我们在这里让dp[i]表示“到位置 i 为止，解码方法的总数”
状态转移方程：
根据最近的一步划分问题
i 位置数字可以选择自己单独解码，也可以选择和 i-1 位置数字组合
如果能够单独解码（1 ~ 9），就相当于延续了 dp[i-1] 所表示的各种解码方法；
如果能和 i-1 位置处的数字组合解码（10 ~ 26），就相当于延续了 dp[i-2] 所表示的各种解码方法；
所以 dp[i] = dp[i-1] + dp[i-2] （这是都能解码的情况，假如不能单独解码，就是 0 + dp[i-2]）
//对我而言写起来还是挺麻烦的……
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
//状态表示
vector<int> dp(n);
//初始化
if (s[0] != '0') dp[0] = 1;
else return 0;
//处理边界情况
if (n == 1) return dp[0];
if (s[0] != '0' && s[1] != '0') dp[1]++;
int t = (s[0]-'0')*10 + s[1] -'0';
if(t>=10 && t<=26) dp[1]++;
//状态转移方程
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];
}
return dp[n - 1];
}
};
在上面的代码中，我们在初始化 s[1] 时显然有些麻烦，接下来对其进行优化，用状态转移方程去解决 s[1] 的值的问题
//优化后代码
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
//状态表示
vector<int> dp(n+1);//开 n+1 个空间，为的是在状态转移方程的步骤中能够处理未优化时的s[1]
//初始化
dp[0] = 1;//显然dp[0]现在就没什么具体含义了，我们暂且称其为“虚拟节点”
//虚拟节点的值一般来说是0，但就题论题，这道题需要满足 s[2] = s[1] + s[0]，自己分析就知道为什么是1了
if (s[0] != '0') dp[1] = 1;
else return 0;
//处理边界情况(自己写的多此一举了)
//if (n == 1) return dp[1];
//状态转移方程
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];
}
return dp[n];
}
};
二、路径问题
例题4：不同路径
不同路径
状态表示：根据此前的经验和题目要求，我们创建一个二维数组，dp[i][j] 表示走到 ( i , j ) 位置有多少种路径
状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
初始化
class Solution {
public:
int uniquePaths(int m, int n) {
//状态表示
vector<vector<int>> dp(m+1, vector<int>(n+1));//●需要注意学习的写法
//初始化
dp[0][1] = 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];
}
};
不同路径 II
//稍加修改即可
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(); int n = obstacleGrid[0].size();
//状态表示
vector<vector<int>> dp(m+1, vector<int>(n+1));
//初始化
dp[0][1] = 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];
if(obstacleGrid[i-1][j-1] == 1) dp[i][j] = 0;
}
}
return dp[m][n];
}
};
例题5：下降路径最小和
下降路径最小和
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
//状态表示，dp表
int m = matrix.size(); int n = matrix[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+2,INT_MAX));
//初始化
for(int i = 0;i <n+2;i++) dp[0][i] = 0;
//状态转移方程
for(int i = 1;i < m+1;i++){
for(int j = 1;j < n+1;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 ret = INT_MAX;
for(int i = 0;i < n+1;i++){
ret = min(ret,dp[m][i]);
}
return ret;
}
};
例题6：地下城游戏 ★
地下城游戏
分析了一通后发现，如果用此前我们常用的 “到某个位置为止……” 去表示状态似乎行不通
所以我们就用 “从某个位置开始……” 去表示状态
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size(); int n = dungeon[0].size();
//dp[i][j]：从[i,j]位置出发到达终点，所需的最低健康点数
vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
//状态转移方程：从[i,j]位置处走出后的健康点数应当大于等于下一步后所需的最低健康点数（中的较小值），以供自己能走到下一步，而为了取得“最低”，我们让它等于即可
//dp[i][j] + dungeon[i][j] >= min(dp[i][j+1],dp[i+1][j+1])
//初始化
//注意：到达右下角的终点后还得活着走出去：dp[i][j] + dungeon[i][j] >= 1
// 右下区域置成最大值(这个在创建dp表时就做了)
dp[m][n-1] = dp[m-1][n] = 1;
for(int i = m-1;i >= 0;i--){
for(int j = n-1;j >= 0;j--){
dp[i][j] = min(dp[i][j+1],dp[i+1][j]) - dungeon[i][j];
//还要注意路上的血包，如果dp[i][j]处血包大到让 从[i,j]位置出发到达终点所需的最低健康点数 变成了负数……
dp[i][j] = max(1,dp[i][j]);
}
}
return dp[0][0];
}
};
三、简单多状态 dp 问题
例题7：按摩师 ★
按摩师
dp[i]：选择到 i 位置时，此时的最长预约时长
i 位置处可以选择接取或者不接取预约 —— 继续细化
f[i] ：选择到 i 位置时，接取预约，此时的最长预约时长
g[i]：选择到 i 位置时，不接取预约，此时的最长预约时长
状态转移方程：
f[i] = g[i-1] + i 位置处预约时长
g[i] = max( f[i-1], g[i-1] )
class Solution {
public:
int massage(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
vector<int> f(n);
auto g = f;
f[0] = nums[0];
for(int i = 1;i < n;i++){
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[n-1],g[n-1]);
}
};
例题8：打家劫舍 II
打家劫舍 II
通过（对第一家的偷窃与否）进行分类讨论，将环形问题变成和 例题7 一样的线性问题
class Solution {
public:
int _rob(vector<int>& nums,int left,int right){
if(left > right) return 0;
int n = nums.size();
vector<int> f(n);
auto g = f;
f[left] = nums[left];
for(int i = left + 1;i <= right;i++){
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[right],g[right]);
}
int rob(vector<int>& nums) {
int n = nums.size();
//偷了第一家，第二家和最后一家就不能偷
return max(nums[0] + _rob(nums,2,n-2),_rob(nums,1,n-1));
}
};
例题9：删除并获得点数
删除并获得点数
可以看出，如果给的数组是连续且数字连续时，这道题就和 例题7 基本无异
我们对数据加以处理，如图所示：
这样就变得基本和 例题7 一模一样了
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
const int n = 10001;
int arr[n] = {0};
for(auto e:nums) arr[e] += e;
vector<int> f(n);
auto g = f;
for(int i = 1;i < n;i++){
f[i] = g[i-1] + arr[i];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[n-1],g[n-1]);
}
};
例题10：粉刷房子
粉刷房子
题不难
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
//dp表：dp[i][j]：到第 i 个房子选择了 j 颜色为止，最小花费
int n = costs.size();
vector<vector<int>> dp(n+1,vector<int>(3));
//状态转移方程：dp[i] = min(dp[i-1][非相邻列1],dp[i-1][非相邻列2]) + costs[i][j]
//不好表示？那就把情况细化一下：
//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]
//dp表为了方便我多开了一行，需要注意dp表和costs的下标
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(min(dp[n][0],dp[n][1]),dp[n][2]);
}
};
例题11：买卖股票的最佳时机含冷冻期 ★
买卖股票的最佳时机含冷冻期
状态表示：dp[i]：第 i 天结束后（到第 i 天为止）的最大利润
细分：创建一个二维数组
dp[i][0]：第 i 天结束后 处于“买入”股票状态 的最大利润
dp[i][1]：第 i 天结束后 处于“可买入”股票状态 的最大利润
dp[i][2]：第 i 天结束后 处于“冷冻期”股票状态 的最大利润
状态转移方程：
箭头起点表示 i-1 天结束时的状态，箭头终点表示经过一天到第 i 天结束后能进入的状态
dp[i][0] = max(dp[i-1][0], dp[i-1][1] – p[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
dp[i][2] = dp[i-1][0] + p[i]
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]);
}
};
例题12：买卖股票的最佳时机 III ★
买卖股票的最佳时机 III
状态表示：
dp[i] ：第 i 天结束后，能获得的最大利润
根据题目要求细化：
f[ii][j]：第 i 天结束后，完成了 j 次交易，此时处于 “买入” 状态，能获得的最大利润
g[ii][j]：第 i 天结束后，完成了 j 次交易，此时处于 “卖出” 状态，能获得的最大利润
状态转移方程：
f[i][j] = max( f[i-1][j], g[i-1][j] – p[i] )
g[i][j] = max( g[i-1][j], f[i-1][j-1] + p[i] )
初始化：
由状态转移方程，g 表只需初始化第一行，f 表需要初始化第一行和第一列
● 我们可以对状态转移方程稍作修改：
g[i][j] = g[i-1][j]
if(j-1>=0) g[i][j] = max( g[i-1][j], f[i-1][j-1] + p[i] )
这样我们就只需要初始化 f 表的第一行
初始化技巧1：加一行或一列
初始化技巧2：加判断
在初始第一行时，如果将需要设置为很小的值的位置设为 INT_MIN，对于这道题而言是不妥的，因为 ：g[i-1][j] – p[i]
● 所以我们使用 -0x3f3f3f3f（INT_MIN的一半） 来代替 INT_MIN
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
const int INF = 0x3f3f3f3f;//Infimum 下确界/最大下界
vector<vector<int>> f(n,vector<int>(3,-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 < 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>=0) g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i]);
}
}
//到最后选出最后一天完成0次、1次、2次交易的最大值
return max(max(g[n-1][0],g[n-1][1]),g[n-1][2]);
}
};
例题13：买卖股票的最佳时机 IV
买卖股票的最佳时机 IV
基本照搬 12
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
k = min(k,n/2);
const int INF = 0x3f3f3f3f;//Infimum 下确界/最大下界
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>=0)
g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i]);
}
}
int ret = -INF;
for(int i = 0; i <= k; i++){
ret = max(ret, g[n-1][i]);
}
return ret;
}
四、子数组、子串系列
例题14：最大子数组和 ★
最大子数组和
状态表示：dp[i]：以 i 位置结尾的所有子数组中的最大和（看清楚这表达的是什么意思）
状态转移方程：
dp[i] = nums[i]（以 i 位置结尾的长度为1的子数组）
dp[i] = dp[i-1] + nums[i]（以 i 位置结尾的长度大于1的子数组）
dp[i] = max(nums[i], dp[i-1] + nums[i])
返回值：整个 dp表 里的最大值
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int ret = dp[0];
for(int i = 1; i < n; i++){
dp[i] = max(nums[i],dp[i-1] + nums[i]);
ret = max(ret, dp[i]);
}
return ret;
}
};
例题15：环形子数组的最大和
环形子数组的最大和
这道题可以分为两种情况：
状态表示：
f[i]：以 i 位置结尾的所有子数组中的最大和
g[i]：以 i 位置结尾的所有子数组中的最小和
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];//处理边界情况
vector<int> f(n);
auto g = f;
f[0] = g[0] = nums[0];
int max_ = INT_MIN;
int min_ = INT_MAX;
for(int i = 1; i < n; i++){
f[i] = max(nums[i],f[i-1]+nums[i]);
max_ = max(max_,f[i]);
g[i] = min(nums[i],g[i-1]+nums[i]);
min_ = min(min_,g[i]);
}
int sum = 0;
for(auto e : nums){
sum += e;
}
//返回值：特殊情况 -- nums中全是负数，此时max_是负数，min_是负数，但sum-min_是0 —— 显然我们应该选择max_（确实难想，想不到就算了吧）
return sum == min_ ? max_ : max(max_,sum - min_);
}
};
多开一个空间写起来能更简洁点
例题16：乘积最大子数组
乘积最大子数组
不算难（至少我能做出来）
class Solution {
public:
int maxProduct(vector<int>& nums) {
//f[i]：以i位置结尾的乘积最大的非空连续子数组
//g[i]：以i位置结尾的乘积最小的非空连续子数组
int n = nums.size();
if(n == 1) return nums[0];//处理边界情况
vector<int> f(n);
f[0] = nums[0];
auto g = f;
int max_ = nums[0];//★
for(int i = 1; i < n; i++){
f[i] = max(max(nums[i],f[i-1]*nums[i]),g[i-1]*nums[i]);
max_ = max(max_,f[i]);
g[i] = min(min(nums[i],f[i-1]*nums[i]),g[i-1]*nums[i]);
}
return max_;
}
};
例题17：乘积为正数的最长子数组长度
乘积为正数的最长子数组长度
不难想，但状态转移方程需要捋清楚
class Solution {
public:
int getMaxLen(vector<int>& nums) {
//f[i]：以i位置结尾的乘积为正数的最长子数组长度
//g[i]：以i位置结尾的乘积为负数的最长子数组长度
int n = nums.size();
vector<int> f(n),g(n);
f[0] = nums[0] > 0 ? 1 : 0;
g[0] = !f[0];
if(nums[0] == 0) f[0] = g[0] = 0;
int max_ = f[0];
//状态转移方程
for(int i = 1; i < n; i++){
//！要注意这里的逻辑
f[i] = nums[i] > 0 ? f[i-1]+1 : (g[i-1] == 0 ? 0 : g[i-1] + 1);//其实只讨论了nums[i] >0 和 <0 的情况，=0 放后面处理
g[i] = nums[i] < 0 ? f[i-1]+1 : (g[i-1] == 0 ? 0 : g[i-1] + 1);
if(nums[i] == 0) f[i] = g[i] = 0;
max_ = max(max_,f[i]);
}
return max_;
}
};
例题18：等差数列划分
等差数列划分
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
//dp[i]：以i位置结尾、是等差数列的子数组的个数
//dp[i]若和dp[i-1]、dp[i-2]形成了等差数列，dp[i] = dp[i-1] + 1
//解释：其中的dp[i-1]表示在 以i-1位置……的子数组 后又加了一个数字，形成了新的等差数列
// 其中的 +1 指的就是 dp[i]、dp[i-1]、dp[i-2] 这个等差数列
//若没有形成，dp[i] = 0;
//如果没形成等差数列 -- dp[i] = dp[i-1]
int n = nums.size();
if(n < 3) return 0;
vector<int> dp(n);
int ret = 0;
int sub1 = nums[1] - nums[0];
int sub2 = nums[2] - nums[1];
if(sub1 == sub2){
dp[2] = 1;
ret = 1;
}
for(int i = 3; i < n; i++){
sub1 = nums[i] - nums[i-1];
sub2 = nums[i-1] - nums[i-2];
if(sub1 == sub2) dp[i] = dp[i-1] + 1;
else dp[i] = 0;
ret += dp[i];
}
return ret;
}
};
例题19：最长湍流子数组 ★
最长湍流子数组
分析：
状态表示：
dp[i]：以 i 位置结尾的所有子数组中，最长湍流子数组的长度
状态转移方程：
dp[i] 与 dp[i-1]：所给的数组 nums[i] 可能 > < == nums[i-1]，这就使得从 nums[i-1] 到 nums[i] 可以上升、下降、平齐 —— 分析不出来，换个状态表示
状态表示：
f[i]：以 i 位置结尾的所有子数组中，最后呈现 “上升” 状态的最长湍流子数组的长度
g[i]：以 i 位置结尾的所有子数组中，最后呈现 “下降” 状态的最长湍流子数组的长度
状态转移方程：
（做例题23回顾这道题时的疑问）为什么 f[i] 在 a>b 时是1不是0 ？明明是下降状态，跟定义的上升完全没关系啊？
由题意，单单一个数也能是湍流数组，可以认为一个数的时候就是万能的状态
初始化：把所有数据全初始化为 1
初始化技巧3
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int n = arr.size();
vector<int> f(n,1),g(n,1);
int ret = 1;
for(int i = 1; i < n; i++){
if(arr[i-1] < arr[i]) f[i] = g[i-1]+1;
else if(arr[i-1] > arr[i]) g[i] = f[i-1]+1;
ret = max(ret,max(f[i],g[i]));
}
return ret;
}
};
例题20：单词拆分 ★
单词拆分
状态表示：
dp[i]：以 i 位置结尾的字符串是否能够被拼接成
状态转移方程：
dp[i]：若 以 j-1 位置结尾的字符串能够被拼接成 且 j 到 i 位置的字符串对应字典中的单词 —— dp[i] = 1
初始化：
显然单独给 dp[0] 初始化有些麻烦，所以增加一个虚拟空间
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
//优化，方便查找
unordered_set<string> hash;
for(auto& s : wordDict) hash.insert(s);
int n = s.size();
vector<bool> dp(n+1);
dp[0] = 1; //保证后序填表正确
s = ' ' + s;//使得下标统一
for(int i = 1; i <= n; i++){
for(int j = i; j >=1; j--){
if(dp[j-1] && hash.count(s.substr(j,i-j+1))){
dp[i] = true;
break;
}
}
}
return dp[n];
}
};
例题21：环绕字符串中唯一的子字符串
环绕字符串中唯一的子字符串
class Solution {
public:
int findSubstringInWraproundString(string s) {
//dp[i]：以位置 i 结尾的子串中有多少不同非空子串在 base 中出现
int n = s.size();
vector<int> dp(n,1);
//状态转移方程：
//dp[i]：单看s[i]肯定可以，和前面组合时，判断s[i]是否为s[i-1]的下一个字母
//若是，dp[i] = dp[i-1] + 1
//但这道题还有一个问题：不能重复
//设想：zabc和abc都以c结尾，而zabc显然包含了abc的所有情况
//——相同字符结尾，只需统计dp[i]较大值即可避免重复，我们用一个数组来实现这个想法
int count[26] = {0};
count[s[0]-'a'] = 1;
for(int i = 1; i < n; i++){
if(s[i] == s[i-1] + 1 || s[i] == 'a' && s[i-1] == 'z') dp[i] = dp[i-1]+1;
count[s[i]-'a'] = max(count[s[i]-'a'],dp[i]);
}
int ret = 0;
for(auto e : count) ret += e;
return ret;
}
};
五、子序列问题
例题22：最长递增子序列
最长递增子序列
不难，甚至我都可以自己写出来（思路有一部分（指再套一层循环）来源于例题20）：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n == 1) return 1;
//dp[i]：以i位置结尾的子序列中的最长递增子序列
vector<int> dp(n,1);
int ret = 0;
for(int i = 1; i < n; i++){
for(int j = i - 1; j >= 0; j--){
if(nums[i] > nums[j]){
dp[i] = max(dp[i],dp[j]+1);
}
}
ret = max(ret,dp[i]);
}
return ret;
}
};
例题23：摆动序列
摆动序列
例题19 最长湍流子数组 的改版，基本没有区别（只是要注意例19是“子数组”，而这里是“子序列”）
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
vector<int> f(n,1),g(n,1);//f[i]:以i位置结尾的向下摆动子序列的最长长度 g[i]:…………
int ret = 1;
for(int i = 1; i < n; i++){
for(int j = i-1; j >=0 ; j--){
if(nums[j] < nums[i]) f[i] = max(f[i], g[j]+1);//没想到自己回顾这道题时竟被这写法给迷惑了，想着为什么不写成f[i] = g[j]+1 …… j=i-1时肯定是这样，但当j为其他值时，形成的相应的子序列有长有短，当然得和当前保存的最长子序列比较看是否要更新最长的数据了……
else if(nums[j] > nums[i]) g[i] = max(g[i],f[j]+1);
}
ret = max(ret,max(f[i],g[i]));
}
return ret;
}
};
例题24：最长递增子序列的个数 ★
最长递增子序列的个数
感觉算不上难……但我就是没做出来（
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
//状态表示：
//len[i]：以i位置结尾的最长递增子序列的长度
//count][i]：以i位置结尾的最长递增子序列的个数
vector<int> len(n,1),count(n,1);
int retlen = 1, retcount = 1;//最终返回的最长递增子序列的长度即其个数
for(int i = 1; i < n; i++){
for(int j = i-1;j >=0; j--){//给自己的注释：这第二层循环正着反着都一样
if(nums[i]>nums[j]){
//i位置的数据能够和此前数据形成递增子序列
if(len[i] < len[j]+1) len[i] = len[j]+1, count[i] = count[j];
else if(len[i] == len[j]+1) count[i]+=count[j];
}
}
if(retlen == len[i]) retcount += count[i];
else if(retlen < len[i]) retlen = len[i], retcount = count[i];
}
return retcount;
}
};
例题25：最长数对链
最长数对链
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
//对原始数组进行预处理（但这里连仿函数都不需要写是我没想到的）
sort(pairs.begin(),pairs.end());
//为什么这样预处理就可以了？试想v1--[1,4]与v2--[2,3]，题目规定了数对数组注定右大于左，所以v1[0]<v2[0]，就注定了v1[0]<v2[1]，v1是不可能跑到v2后面去形成数对链的
int n = pairs.size();
vector<int> dp(n,1);//dp[i]：以i位置数对数组结尾的最长数对链的长度
int ret = 1;
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
if(pairs[i][0] > pairs[j][1]){
dp[i] = max(dp[i],dp[j]+1);
}
}
ret = max(ret,dp[i]);
}
return ret;
}
};
这是写给自己看的：预处理！一定要学会这种思想！
例题26：最长定差子序列 ★
最长定差子序列
本来觉得挺简单的，直到发现自己的解答最终超时了（
分析：
状态表示：dp[i]：以 i 位置结尾的所有子序列中，最长的等差子序列的长度
状态转移方程：
设 i 位置的数字为 a，题目已经给了我们等差子序列的差值difference，所以我们只要往前去找满足 b – a = difference 的元素 b；
● i 位置前不存在 b：dp[i] = 1
● i 位置前存在 b：简单分析可知，我们只需要找到之前最靠近 i 位置的 b 并获取 b 所在位置的状态 dp[j]，dp[i] = dp[j]+1
—— 如何去寻找最近的 b 并获取相应的 dp[j] ？比起套一层循环，我们可以把 b 和 dp[j] 放进 哈希表 来优化
—— 甚至我们可以不要 dp 表，直接在哈希表中做动态规划
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
unordered_map<int,int> hash;//arr[i] - dp[i]
hash[arr[0]] = 1;
int ret = 1;
for(int i = 1; i < arr.size(); i++){
hash[arr[i]] = hash[arr[i]-difference] + 1;//没找到返回0，+1后正好也是我们想要的值
ret = max(ret,hash[arr[i]]);
}
return ret;
}
};
例题27：最长的斐波那契子序列的长度 ★
最长的斐波那契子序列的长度
分析：
若以 dp[i] 表示以 i 位置结尾的最长的斐波那契子序列的长度，在推导状态转移方程时我们发现 dp[i]的推导 与前面的斐波那契子序列有关，我们起码得知道当前位置的值、前面能和当前位置组成斐波那契序列的两个值，但显然这个状态表示做不到
状态表示：
dp[i][j]：以 i j 两个位置（i < j）结尾的最长的斐波那契子序列的长度
示意图：
状态转移方程：
设 i 位置的数为 b，j 位置的数为 a
有了 b a 我们就可以推出能与它们结合成斐波那契数列的数字 c（设位置为 k）
（如果 c >= b）dp[i][j] = 2
（如果 c < b 且 c 存在）dp[i][j] = dp[k][i] + 1
（如果 c < b 且 c 不存在）dp[i][j] = 2
优化：寻找数字 a 所在的位置，比起套一层循环，哈希表更好
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size();
unordered_map<int, int> hash;
for(int i = 0; i < n; i++) hash[arr[i]] = i;
//需要注意的是，这道题明确说明了给的数组是严格递增（不重复，递增）的，所以我们可以这么写，不同的题情况不同写法也可能不同
vector<vector<int>> dp(n,vector<int>(n,2));
int ret = 2;
for(int j = 2; j < n; j++){
for(int i = 1; i < j; i++){
int a = arr[j] - arr[i];
if(a < arr[i] && hash.count(a)) dp[i][j] = dp[hash[a]][i]+1;
//个人问题：为什么hash.count(a)不能替换为hash[a]？
//这里哈希映射的关系是 数据 - 相应的下标，如果 a 的下标是 0，显然a存在，但hash[a]的结果是0
ret = max(ret,dp[i][j]);
}
}
return ret < 3 ? 0 : ret;
}
};
例题28：最长等差数列 ★
最长等差数列
细节很多的题
分析后可知，就像例题27一样，dp[i]是解决不了问题的，所以用 dp[i][j] 表示以 i j （i < j）位置结尾的最长等差数列的长度
状态转移方程：
分析知，我们根据 i j 位置元素算得 a 可以组成等差数列，如果 i 位置前有多个 a，最靠近 i 位置的 a，以其和 i 位置为结尾的最长等差子序列一定最长
但这道题不像上一题一样数组严格递增，提前把数据和相应位置都映射到哈希表里以快速找到最靠近 i 位置的 a 的方式也不可取，但如果不优化的话时间复杂度高达 O(N^3)
两种优化思路：
- 用哈希表存储 数据 和 数据所在的位置（位置用数组存储）
—— 但存在问题：找到数据对应的位置数组后也得遍历数组去寻找最靠近 i 位置的位置，如果数据量过大，复杂度仍是O(N^3) - 一边dp，一边填写哈希表：
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
unordered_map<int,int> hash;
hash[nums[0]] = 0;
int n = nums.size();
vector<vector<int>> dp(n,vector<int>(n,2));
int ret = 2;
//还要注意循环始末：
for(int i = 1; i < n; i++){//固定倒数第二个数
for(int j = i+1; j < n; j++){//枚举倒数第一个数
// int sub = nums[j] - nums[i];
// int a = nums[i] - sub;
int a = 2*nums[i] - nums[j];
if(hash.count(a))
dp[i][j] = dp[hash[a]][i] + 1;
ret = max(ret,dp[i][j]);
}
hash[nums[i]] = i;
}
return ret;
}
};
例题29：等差数列划分 II – 子序列
等差数列划分 II – 子序列
● 这道题没说统计的等差子序列不能重复
与上一题不同的是，上一题统计最长长度，这一题统计等差数列个数
状态表示：
dp[i][j]：以 i j 位置元素结尾的数组中等差子序列的数目
状态转移方程：
i 位置元素 b，j 位置元素 a，算得元素 c = 2b – a，设 c 位置为 k
（如果k位置存在且 k < i ）dp[i][j] = dp[k][i] + 1
初始化：
不用初始化，全 0 即可
优化：
使用了上一题的第一种思想：用哈希表存储 数据 和 数据所在的位置（位置用数组存储）
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
unordered_map<long long,vector<int>> hash;//-2^31 <= nums[i] <= 2^31 - 1
for(int i = 0;i<n;i++) hash[nums[i]].push_back(i);//写法需要注意
vector<vector<int>> dp(n,vector<int>(n));//dp[i][j]：以 i j 位置元素结尾的数组中等差子序列的数目
int sum = 0;
//循环写成for(int j = 2; j < n; j++)
// for(int i = 1; i < j; i++)
//（老师是怎么写的）也没什么问题
for(int i = 1; i < n; i++){
for(int j = i+1; j < n;j++){
long long a = (long long)2*nums[i] - nums[j];//需要注意数据类型
if(hash.count(a)){
for(auto k : hash[a]){
if(k < i) dp[i][j] += (dp[k][i] + 1);
}
}
sum += dp[i][j];
}
}
return sum;
}
};
六、回文串问题
例题30：回文子串 ★
回文子串
对于回文子串的题目而言，动态规划算法能解，但不是最优解，还有其他的解决方式：
1.中心扩展算法
2.马拉车算法（不建议重点学习，难学且太局限了，只能解决回文子串的问题）
3.动态规划
不过我们这里只用动态规划处理
动态规划处理思想：将所有子串是否是回文的信息，用dp表存储
如何表示 “所有的子串”（子字符串 是字符串中的由连续字符组成的一个序列） ：
状态表示：
dp[i][j]：i 位置到 j 位置（i <= j）的字符串是否为回文子串（true / false）
状态转移方程：
如果 s[i] != s[j]：dp[i][j] = false
如果 s[i] == s[j] :
（i == j）dp[i][j] = ture
（i == j -1）dp[i][j] = ture
（ i < j-1）dp[i][j] = dp[i+1][j-1]
初始化：
不用初始化（开始全为0–false），dp[i][j] = dp[i+1][j-1] 可能越界的问题也被前两个判断排除了
填表顺序：根据dp[i][j] = dp[i+1][j-1]，我们需要先填充左下角的值，所以需要从下往上填表
class Solution {
public:
int countSubstrings(string s) {
int n = s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
int ret = 0;
for(int i = n - 1; i >= 0; i--){
for(int j = i; j < n; j++){
if(s[i] == s[j])
dp[i][j] = i < j - 1 ? dp[i+1][j-1] : true;
if(dp[i][j]) ret++;
}
}
return ret;
}
};
例题31：最长回文子串
最长回文子串
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
int begin = 0;
int len = 0;
for(int i = n - 1; i >= 0; i--){
for(int j = i; j < n; j++){
if(s[i] == s[j])
dp[i][j] = i < j - 1 ? dp[i+1][j-1] : true;
//如果 i 位置到 j 位置（i <= j）的字符串是回文子串 且 该回文子串比此前记录的最长回文子串长：
if(dp[i][j] && j - i + 1 > len){
len = j - i + 1;
begin = i;
}
}
}
return s.substr(begin,len);
}
};
例题32：分割回文串 II
分割回文串 II
这道题类似 例题20：单词拆分，思路与以上几道回文子串题不同
class Solution {
public:
int minCut(string s) {
//根据以往的经验，令 dp[i] 表示以 i 位置为结尾的子串的最少分割次数
//说来此前都没太注意，一般说 以 i 位置为结尾 指的是：从开始一直到i位置为止
//状态转移方程：s[0,i]为回文 -- dp[i] = 0（不用分割）
// s[0,i]不是回文 -- 取 0-i 之间某一位置 j
//如果j~i是回文 -- dp[i] = min(dp[j-1]+1,dp[i]) 如果j~i不是回文，过
//优化：此前的做法，用dp表存储所有子串是否为回文字符串的信息
int n = s.size();
vector<vector<bool>> isPal(n,vector<bool>(n));//palindromic:回文
for(int i = n-1; i >= 0; i--){
for(int j = i; j < n; j++){
if(s[i] == s[j])
isPal[i][j] = i < j - 1 ? isPal[i+1][j-1] : true;
}
}
vector<int> dp(n,INT_MAX);
for(int i = 0; i < n; i++){
if(isPal[0][i]) dp[i] = 0;
else{
for(int j = 1; j <= i; j++){
if(isPal[j][i])
dp[i] = min(dp[i],dp[j-1]+1);
}
}
}
return dp[n-1];
}
};
例题33：最长回文子序列 ★
最长回文子序列
状态表示：
dp[i]：以 i 位置为结尾的子序列中最长回文子序列的的长度
状态转移方程：
分析不出来，因为无从得知前面的序列是什么样子，也不知道加上 s[i] 后序列会变成什么样子 – 换个状态表示
状态表示：
dp[i][j]：以 i 位置开始，j 位置结尾的子序列中最长回文子序列的的长度
● 新的经验：表示一段区间
状态转移方程：
如果 s[i] == s[j]
1.（i == j）dp[i][j] = 1
2.（i == j – 1）dp[i][j] =2
3.（i < j-1）dp[i][j] = dp[i+1][j-1] + 2
如果 s[i] != s[j]
dp[i][j] = max( dp[i+1][j], dp[i][j-1] )
初始化：
不用初始化：根据状态转移方程，dp[i][j] = dp[i+1][j-1] + 2 和 dp[i][j] = max( dp[i+1][j], dp[i][j-1] ) 可能导致越界，但可能越界的数据都被（i == j）和（i == j – 1）的判断解决了
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n,vector<int>(n));
//从左到右，从下往上
for(int i = n-1; i >= 0; i--){
for(int j = i; j < n; j++){
if(s[i] == s[j]){
if(i == j) dp[i][j] = 1;
else if(i == j - 1) dp[i][j] = 2;
else if(i < j - 1) dp[i][j] = dp[i+1][j-1] + 2;
}
else{
dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
}
}
}
return dp[0][n-1];//因为是 子 序 列 ，所以从头到尾必然能组成最长的回文子序列
}
};
例题34：让字符串成为回文串的最少插入次数 ★
让字符串成为回文串的最少插入次数
活学活用此前几道题的话这道题应该不难 —— 但我没做出来（
使用前面用 i j 表示字符串的一段区间的思路
状态表示：
dp[i][j]：i j 区间内让字符串成为回文串的最少插入次数
状态转移方程：
如果 s[i] == s[j]：
（i == j || i == j-1）dp[i][j] = 0
（i < j-1）dp[i][j] = dp[i+1][j-1]
如果 s[i] != s[j]：
dp[i][j] = min(dp[i+1][j]+1, dp[i][j-1]+1)
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
vector<vector<int>> dp(n,vector<int>(n));
// 如果 s[i] == s[j]：
// （i == j || i == j-1）dp[i][j] = 0
// （i < j-1）dp[i][j] = dp[i+1][j-1]
// 如果 s[i] != s[j]：
// dp[i][j] = min(dp[i+1][j]+1, dp[i][j-1]+1)
for(int i = n-1; i >= 0; i--){
for(int j = i; j < n; j++){
if(s[i] == s[j]){
if(i == j || i == j-1) dp[i][j] = 0;//其实可以不用写（毕竟本来就是0）
else if(i < j-1) dp[i][j] = dp[i+1][j-1];
}
else{
dp[i][j] = min(dp[i+1][j]+1, dp[i][j-1]+1);
}
}
}
return dp[0][n-1];
}
};
七、两个数组的 dp
例题35：最长公共子序列 ★
最长公共子序列
据老师所述的超经典的一道题，我们许多的经验都由这道题而来
状态表示：
对于两个字符串的问题：
1.选取第一个字符串 [0, i] 区间以及第二个字符串 [0, j] 区间作为研究对象
2.根据题目要求确定状态表示
dp[i][j]：s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内所有的子序列中，最长的公共子序列的长度
状态转移方程：
首先需要明白的是：若s[i] == s[j] == x，则 s1 的 [0, i] 区间以及 s2 的 [0, j] 区间内所有的子序列中，最长的公共子序列一定是以最后这个 x 结尾的
反证法：
如果其中一个（以 s1 为例）的最长公共子序列的结尾是其内部的某个数，显然这个数肯定是 x，那么 s1 最后的 x 显然也能充当最长公共子序列的结尾；
如果两个字符串的最长公共子序列的结尾都是内部的某个数，s1、s2 的末尾是两个相同的 x，显然也能接上成为最长公共子序列的结尾
如果 s[i] == s[j]：dp[i][j] = dp[i-1][j-1] + 1
如果 s[i] != s[j]：dp[i][j] = max( dp[i][j-1], dp[i-1][j], dp[i-1][j-1] )（分析可知，这道题里最后一种情况已被前两种情况包含，但因为这道题只是求最大长度，这么写并无影响（当然，删掉更优））
初始化：
首先，关于字符串的 dp 问题，空串是有研究意义的；然后，突然说这个是因为如果我们引入空串的概念，是可以方便我们去初始化的
本来我们需要将左边第一列和上面第一行初始化，但若我们增添一行一列，将格外多出的部分当做空串并设为 0（含义：连数都没有自然也就没有公共子序列），我们的初始化就完成了
填表顺序：从上到下，从左向右
返回值：dp[m][n]（增添一行一列后，m：s1的长度，n：s2的长度）
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
text1 = " " + text1; text2 = " " + text2;//●统一下标
vector<vector<int>> dp(m+1,vector<int>(n+1));
//从上向下，从左往右
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(text1[i] == text2[j]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max( dp[i][j-1], dp[i-1][j]);
}
}
return dp[m][n];
}
};
例题36：不相交的线
不相交的线
分析：可以绘制的最大连线数中连在一起的数字，就是两个数组的 最长公共子序列
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.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++){
if(nums1[i-1] == nums2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
};
例题37：不同的子序列 ★
不同的子序列
我的错误解法（最后超时了）：
class Solution {
public:
int numDistinct(string s, string t) {
const int MOD = 1e9 + 7;
//dp[i][j]：s的以i位置结尾的所有子序列中有多少能表示t以j位置结尾的子串（做这么多题了，想必你能分清子序列和子串的区别）
//s[i] == t[j] dp[i][j] += dp[0 ~ i-1][j-1]
//s[i] != t[j] dp[i][j] = 0
int m = s.size(), n = t.size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
dp[0][0] = 1;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(s[i-1] == t[j-1])
for(int k = 0; k < i; k++)
dp[i][j] = (dp[i][j] + dp[k][j-1])% MOD;
else dp[i][j] = 0;
}
}
int ret = 0;
for(int i = 1; i <= m; i++){
ret = (ret + dp[i][n])% MOD;
}
return ret % MOD;
}
};
老师的讲解：
状态表示：
dp[i][j]：s 字符串 [0, j] 区间内所有的子序列中，有多少 t 字符串 [0,i] 区间内的子串
状态转移方程：
（对最后一个位置进行分析：）根据 s 的子序列的最后一个位置包不包含 s[j]
为什么说是包不包含 —— [0, j] 区间内所有的子序列必然有的含有 s[j] 而有的没有
包含：若 s[j] == t[i]，dp[i][j] = dp[i-1][j-1]（s最后一个位置 i 的数据正好等于 t 最后一个位置 j 的数据，看此前的情况）
不包含：dp[i][j] = dp[i][j-1]（s最后一个位置 i 不靠谱，往 i 位置之前找有没有与位置 j 相等的数据）
初始化：
引入空串
需要注意引入空串后要让其中的值保证后续填表正确，要注意下标
class Solution {
public:
int numDistinct(string s, string t) {
int MOD = 1e9 + 7;
int m = t.size(), n = s.size(); //取好 m n 对应 i j
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int j = 0; j <= n; j++) dp[0][j] = 1;//正确使用 i j 表示行列让代码看起来更直观明了
//dp[i][j]：s 字符串 [0, j] 区间内所有的子序列中，有多少 t 字符串 [0,i] 区间内的子串
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
if(s[j-1] == t[i-1]) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
}
}
return dp[m][n] % MOD;
}
};
例题38：通配符匹配 ★
通配符匹配
状态表示：
dp[i][j]：p[0, j] 区间内的子串能否匹配 s[0, i] 区间内的子串
状态转移方程：
（根据最后一个位置的情况，分情况讨论）
如果 p[j] 是普通字符：若 p[j] == s[i] 且 dp[i-1][j-1] == true -> dp[i][j] = true
如果 p[j] 是 ’ ? ’ ：若 dp[i-1][j-1] == true -> dp[i][j] = true
如果 p[j] 是 ’ * ‘：看 * 表示 空串/1个字符/2个字符……n个字符时 dp[i-n][j-1] 的值（直到 dp[i-n][j-1] == true 或是 走完所有情况）
● 优化（针对 p[j] == ’ * ’ 的情况）：
思路一：数学思维
p[j] == ’ * ’ 时，dp[i][j] = dp[i][j-1] || dp[i-1][j-1] || dp[i-2][j-1] ||……
我们发现 dp[i-1][j] = dp[i-1][j-1] || dp[i-2][j-1] || ……
替换得到：dp[i][j] = dp[i][j-1] || dp[i-1][j]
思路二：根据状态表示及实际情况，优化状态转移方程（纯废话，但确实就是这个道理）
p[j] == ’ * ’ 时
若 * 表示空串，dp[i][j] 的值取决于 dp[i][j-1]
若 * 表示1个字符，dp[i][j] 的值取决于 dp[i-1][j] （认为 * 仍然存在，只是从其中分离了一个字符出来）
如果这样划分情况，显然，dp[i-1][j] 的确定也经过了相同的步骤（即本应考虑的 * 表示 2个字符的情况 其实包含在了 dp[i-1][j] 的计算中）
故：dp[i][j] = dp[i][j-1] || dp[i-1][j]
初始化：
引入空串
统一下标：p = ” ” + p; s = ” ” + s;
dp[0][0] = true（空串匹配空串）
第一行：试想，p[1] = ’ * ‘，那么 dp[0][1] = true（p[0, 1] 区间内的子串能否匹配 s[0, 0] 区间内的子串）
如果 p[2] 仍为 * ，那么 dp[0][2] =true
但到了p[3] 突然不是 * ，那么从 dp[0][3] 到第一行末尾就都是 false 了
第一列：全为 false
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
s = " " + s; p = " " + p;
vector<vector<bool>> dp(m+1,vector<bool>(n+1));
dp[0][0] = true;
for(int j = 1; j <= n; j++){
if(p[j] == '*') dp[0][j] = true;
else break;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(p[j] == '*')
dp[i][j] = dp[i-1][j] || dp[i][j-1];
else
dp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i-1][j-1];
}
}
return dp[m][n];
}
};
例题39：正则表达式匹配 ★
正则表达式匹配
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
s = ' ' + s; p = ' '+ p;//统一下标
vector<vector<bool>> dp(m+1,vector<bool>(n+1));
dp[0][0] = true;
for(int j = 2; j <= n; j += 2){
if(p[j] == '*') dp[0][j] = true;
else break;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(p[j] == '*')
dp[i][j] = dp[i][j-2] || (p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j];
else
dp[i][j] = (p[j] == '.' || p[j] == s[i]) && dp[i-1][j-1];
}
}
return dp[m][n];
}
};
例题40：交错字符串 ★
交错字符串
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
//预处理（统一下标）：s1 = ' ' + s1; s2 = ' ' + s2; s3 = ' ' + s3;
//dp[i][j]:s1中[1,i]区间内的字符串以及s2中[1,j]区间内的字符串能否拼接成s3[1,i+j]区间内的字符串
int m = s1.size(), n = s2.size();
if(m + n != s3.size()) return false;
s1 = ' ' + s1; s2 = ' ' + s2; s3 = ' ' + s3;
vector<vector<bool>> dp(m+1,vector<bool>(n+1));
dp[0][0] = true;
for(int i = 1; i <= m; i++){
if(s1[i] == s3[i]) dp[i][0] = true;
else break;
}
for(int j = 1; j <= n; j++){
if(s2[j] == s3[j]) dp[0][j] = true;
else break;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
// if(s1[i] == s3[i+j]) dp[i][j] = dp[i-1][j];
// if(s2[j] == s3[i+j]) dp[i][j] = dp[i][j] || dp[i][j-1];
dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) ||
(s2[j] == s3[i + j] && dp[i][j - 1]);
}
}
return dp[m][n];
}
};
例题41：两个字符串的最小ASCII删除和 ★
两个字符串的最小ASCII删除和
问题转化：找两个字符串的所有公共子序列中，ASCII码和最大的公共子序列
“正难则反”
dp[i][j]：s1的 [0, i] 区间与 s2的 [0, j] 区间中所有公共子序列中，最大ASCII码和
根据最后一个位置的情况，分情况讨论（要考虑到所有情况）：
1.最长公共子序列中有 s1[i] 和 s2[j]：（若 s1[i] == s2[j]）dp[i][j] = dp[i-1][j-1] + s1[i]
2.最长公共子序列中有 s1[i] 无 s2[j]：dp[i][j] = dp[i-1][j]（dp[i-1][j] 实际上包含了情况2和4，但因为要求的是最大值，只需要保证数据 “不漏”，“不重” 不在我们的考虑范围内）
3.最长公共子序列中无 s1[i] 有 s2[j]：dp[i][j] = dp[i][j-1]（同 2）
4.最长公共子序列中无 s1[i] 无 s2[j]：dp[i][j] = dp[i-1][j-1]（因为2、3都包含了4，4可以不写）
//注意下标
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int m = s1.size(), n = s2.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(s1[i-1] == s2[j-1] ? dp[i-1][j-1] + s1[i-1] : 0, max(dp[i][j-1], dp[i-1][j]));
}
}
int sum = 0;
for(auto ch : s1) sum += ch;
for(auto ch : s2) sum += ch;
return sum - 2*dp[m][n];
}
};
例题42：最长重复子数组 ★
最长重复子数组
分析：若我们在状态表示选取 [0, i] 区间内所有的子数组研究，我们知道，对于子数组，dp[i+1] 肯定是从 dp[i] 而来的（i+1位置的数只能选择跟不跟在i位置的数字后），显然我们选取的状态表示范围太大
状态表示：
dp[i][j]：nums1中以 i 位置为结尾的所有子数组 以及 nums2中以 j 位置为结尾的所有子数组 中最长重复子数组的长度
状态转移方程：
根据最后一个位置的情况，分情况讨论
nums[i] != nums[j] -> dp[i][j] = 0
nums[i] == nums[j] -> dp[i-1][j-1] + 1
返回值：dp表中的最大值
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
int ret = 0;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = 0;
ret = max(ret, dp[i][j]);
}
}
return ret;
}
};
八、01 背包问题
背包问题简介：
地上一堆物品，挑选一些放入背包中，能挑选出的最大的价值是多少？
物品具有属性（价值、个数、重量等），背包也具有属性（容量、承重等）
根据物品的个数，主要分两类问题：
各物品只有一个 —— 01背包问题
各物品无穷多个 —— 完全背包问题
根据背包的容量，也会有两类问题：背包不必装满 与 背包必须装满
不像此前的大部分题目，我们是不需要优化的，而背包问题不同，基本所有的背包问题都是需要优化的
例题43：【模板】01背包
【模板】 01背包
dp[i]：从前 i 个物品中挑选，能选出的最大价值
—— 推不出状态转移方程，因为在分析第 i 个物品可不可以选时，没有背包体积做依据
（1）求这个背包至多能装多大价值的物品？
状态表示：dp[i][j]：从前 i 个物品中挑选，总体积不超过（<=） j（说不超过是因为第一个问题不必装满背包），所有的选法中，能选出的最大价值
状态转移方程：
不选 i 物品时，dp[i][j] = dp[i-1][j]
选 i 物品时（且 j – v[i] >= 0），dp[i][j] = w[i] + dp[i-1][j-v[i]]
dp[i][j] 取最大值
（2）若背包恰好装满，求至多能装多大价值的物品？
状态表示：dp[i][j]：从前 i 个物品中挑选，总体积为 j，所有的选法中，能选出的最大价值
状态转移方程：
不选 i 物品时，dp[i][j] = dp[i-1][j]
选 i 物品时（且 j – v[i] >= 0），dp[i][j] = w[i] + dp[i-1][j-v[i]]
dp[i][j] 取最大值
但显然 dp[i-1][j] 和 dp[i-1][j-v[i]] 都存在选不到的情况（所选物品凑不出相应的体积），设这种情况的值为 -1 （不能是 0 ，因为 0 的含义是不选物品）
对它们进行判断后才能考虑是否赋值给 dp[i][j]
初始化：
第一问全 0 即可，第二问：
#include <iostream>
#include<vector>
using namespace std;
int main(){
int n, V;
cin >> n >> V;
vector<int> v, w;
int vi, wi;
while(cin >> vi >> wi){
v.push_back(vi);
w.push_back(wi);
}
//dp1[i][j]：从前 i 个物品中挑选，总体积不超过（<=） j（说不超过是因为第一个问题不必装满背包），能选出的最大价值
vector<vector<int>> dp1(n+1,vector<int>(V+1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= V; j++){
dp1[i][j] = dp1[i-1][j];
if(j - v[i-1] >= 0) dp1[i][j] = max(dp1[i][j], w[i-1] + dp1[i-1][j-v[i-1]]);
}
}
cout << dp1[n][V] << endl;
//dp2[i][j]：从前 i 个物品中挑选，总体积为 j，能选出的最大价值
vector<vector<int>> dp2(n+1,vector<int>(V+1));
for(int j = 1; j <= V; j++) dp2[0][j] = -1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= V; j++){
dp2[i][j] = dp2[i-1][j];
if(j - v[i-1] >= 0 && dp2[i-1][j-v[i-1]] != -1)
dp2[i][j] = max(dp2[i][j], w[i-1] + dp2[i-1][j-v[i-1]]);
}
}
cout << (dp2[n][V] == -1 ? 0 : dp2[n][V])<< endl;
return 0;
}
优化：
1.利用滚动数组做空间上的优化
2.直接在原始代码上稍加修改即可
由状态转移方程可知，dp[i][j] 只与上一行的状态有关
我们可以通过使用一上一下两个数组，下面的数组填满后将上面的数组滚动至下面，继续填写
或者可以直接用一个数组（这样的话就只剩一行，就变成 dp[j] 了（横坐标没了））（还要注意应当从右向左遍历）
#include <iostream>
#include<vector>
using namespace std;
int main(){
int n, V;
cin >> n >> V;
vector<int> v, w;
int vi, wi;
while(cin >> vi >> wi){
v.push_back(vi);
w.push_back(wi);
}
//空间优化
vector<int> dp1(V+1);
for(int i = 1; i <= n; i++){
for(int j = V; j >= v[i-1]; j--){//需要注意这里变成了从右向左遍历
dp1[j] = max(dp1[j], w[i-1] + dp1[j-v[i-1]]);
}
}
cout << dp1[V] << endl;
vector<int> dp2(V+1);
for(int j = 1; j <= V; j++) dp2[j] = -1;
for(int i = 1; i <= n; i++){
for(int j = V; j >= v[i-1]; j--){
if(dp2[j-v[i-1]] != -1)
dp2[j] = max(dp2[j], w[i-1] + dp2[j-v[i-1]]);
}
}
cout << (dp2[V] == -1 ? 0 : dp2[V])<< endl;
return 0;
}
例题44：分割等和子集
分割等和子集
● 问题转化：能否从数组中选出一些数，让它们的和为 sum / 2
状态表示：
dp[i][j]：在前 i 个数中挑选，所有选法中，和能否为 j
状态转移方程：
不选 i ：dp[i][j] = dp[i-1][j]
选 i：若 j – nums[i] >= 0，dp[i][j] = dp[i-1][j-nums[i]]
分析元素选或不选 —— 01背包问题
初始化：
增添一行一列，第一列全 true，第一行（除了第一个元素）全 false
返回值：
dp[n][sum/2]
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(auto e : nums) sum += e;
if(sum % 2) return false;//奇数
int n = nums.size();
vector<vector<bool>> dp(n+1,vector<bool>(sum%2+1));
for(int i = 0; i <= n; i++) dp[i][0] = true;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= sum%2; j++){
dp[i][j] = dp[i-1][j];
if(j - nums[i] >= 0) dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
}
}
return dp[n][sum%2];
}
例题45：目标和 ★
目标和
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
//问题转化：在数字前加+-号，使得 正数和a - 负数和的绝对值b = target
//知：a+b=sum , a-b=target -> a=(sum+target)/2
//问题变成：选取数字，使其和为 a（只要能得到a，剩下的数字就能算出b，进而得到target）
//状态表示：dp[i][j]：从前 i 个数字中挑选，和为 j 的表达式数—— 01背包问题
//状态转移方程：不选 i 数 dp[i][j] += dp[i-1][j]
//选 i 数：（若j>=nums[i]）dp[i][j] += dp[i-1][j-nums[i]]
int sum = 0;
for(auto e : nums) sum += e;
int a = (sum+target)/2;
if(a<0||(sum+target)%2 != 0) return 0;//如果a不是整数 或 a作为所有整数的和却不是正数
int n = nums.size();
vector<vector<int>> dp(n+1,vector<int>(a+1));
//初始化
dp[0][0] = 1;//不选
//要注意的是，第一行除了第一个位置全为 0 好理解，但第一列（除了第一个位置）和之前问题不同的是，
//数组里的数是可以为 0 的，如果第一个数为 0，那么dp[0][1] 就是2，所以第一列是需要计算的
//显然，第一列不需要我们去初始化，直接加入到计算中也不会越界 —— j>=nums[i]的判断使其不会遇到越界的情况
for(int i = 1; i <= n; i++){
for(int j = 0; j <= a; j++){
dp[i][j] += dp[i-1][j];
if(j>=nums[i-1]) dp[i][j] += dp[i-1][j-nums[i-1]];
}
}
return dp[n][a];
}
};
例题46：最后一块石头的重量 II ★
最后一块石头的重量 II
问题转化：
有 [a,b,c,d,e] 这样一个数组，如果得到最小重量的步骤是先磨 a c（a>c）得到 a-c，再磨 b e（e>b）得到 e-b，再磨 d a-c （d>a-c）得到 d-a+c，（e-b>d-a+c）最后得到 e-b-d+a-c
可以看出归根结底不过是 正数和 – 负数绝对值的和，要求结果最小
当正数和最接近负数绝对值的和时结果最小 —— 在数组中选择一些数，使得这些数的和尽可能接近 sum/2
石块数量 – 物品数量
石块质量 – 物品体积
石块质量 – 物品价值
典型的01背包问题
dp[i][j]：从前 i 个中选取，质量不超过 j 时，此时的最大质量
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size();
int sum = 0;
for(auto e : stones) sum += e;
int m = sum/2;
vector<vector<int>> dp(n+1,vector<int>(m+1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = dp[i-1][j];
if(j>=stones[i-1])
dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
}
}
//返回值：负数和的绝对值(>=sum/2) - 正数和(dp[n][m]<=sum/2) -> 正数和 + 负数和的绝对值 = sum
//负数和的绝对值 = sum - 正数和(dp[n][m])
//返回值：sum - 2*dp[n][m]
return sum-2*dp[n][m];
}
};
九、完全背包问题
例题47：【模板】完全背包 ★
【模板】完全背包
（1）求这个背包至多能装多大价值的物品？
状态表示：
从前 i 个物品中选，总体积不超过 j，所有选法中的最大价值
状态转移方程：
不选 i 物品： dp[i][j] = dp[i-1][j]
选 1 个 i 物品（j >= v[i]）：dp[i][j] = dp[i-1][j-v[i]]+w[i]
选 2 个 i 物品（j >= 2 * v[i]）：dp[i][j] = dp[i-1][j-2*v[i]] + 2 * w[i]
………………
dp[i][j] = max( dp[i – 1][j], dp[i – 1][j – v[i]] + w[i], dp[i – 1][j – 2 * v[i]] + 2 * w[i], …… , dp[i – 1][j – k * v[i]] + k * w[i]) （式1）
● 分析优化（仿照 例题38：通配符匹配 的思想）：
dp[i][j – v[i]] = max( dp[i – 1][j – v[i]], dp[i – 1][j – 2 * v[i]] + w[i], …… , dp[i – 1][j – k * v[i]] + (k-1) * w[i] ) （式2）
在 式2 的左右两侧 + w[i] 变成
dp[i][j – v[i]] + w[i]= max( dp[i – 1][j – v[i]] + w[i], dp[i – 1][j – 2 * v[i]] + 2 * w[i], …… , dp[i – 1][j – k * v[i]] + k * w[i] ) （式3）
将 式3 代入 式1 后得到：
dp[i][j] = max( dp[i – 1][j], dp[i][j – v[i]] + w[i] ) （j >= v[i]）
初始化：
增添一行一列，第一列可以放进计算不用初始化（有 j >= v[i] 的判断，不用担心越界的情况），根据第一行的含义，全为 0 —— 也不用初始化
（2）若背包恰好装满，求至多能装多大价值的物品？
和 01背包一样，对（1）稍加修改：
状态表示：
从前 i 个物品中选，总体积为 j，所有选法中的最大价值
状态转移方程：
凑不出体积 j 时 dp[i][j] = -1
除了进行 j >= v[i] 的判断还要判断 dp[i][j – v[i]] 是否为 -1
初始化：
初始化情况和 01背包第二问 一样
返回值：
若最终为 -1 ，要注意返回 0
#include <iostream>
using namespace std;
#include<string.h>
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main() {
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 = 0; j <= V; j++){
dp[i][j] = dp[i-1][j];
if(j >= v[i])
dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;
memset(dp,0,sizeof(dp));//全部重置为0
for(int j = 1; j <= V; j++)
dp[0][j] = -1;
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-v[i]] != -1)
dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]);
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) <<endl;
return 0;
}
空间优化：
同 01背包 用一行解决问题（但不同的是，分析知完全背包需要从左向右遍历）
//基本上和 01背包 无异
#include <iostream>
using namespace std;
#include<string.h>
const int N = 1010;
int n, V, v[N], w[N];
int dp[N];
int main() {
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;
memset(dp,0,sizeof(dp));//全部重置为0
for(int j = 1; j <= V; j++)
dp[j] = -1;
for(int i = 1; i <= n; i++){
for(int j = v[i]; j <= V; j++){
if(dp[j-v[i]] != -1)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << (dp[V] == -1 ? 0 : dp[V]) <<endl;
return 0;
}
代码优化：
有些题解是没有 dp[i][j-v[i]] != -1 / dp[j-v[i]] != -1 这一判断的，只需要让 dp[j – v[i]] + w[i] 极小以确保其不可能大于 dp[j] 即可 —— 初始化时不设为 -1，设为 -0x3f3f3f3f
例题48：零钱兑换
零钱兑换
和之前凑零钱的问题相比，这道题并未给出不同面额的硬币的具体情况——面额多少？有多少种？
所以不能用之前的方法解决这个问题
状态表示：
模仿完全背包：dp[i][j]
从前 i 个物品中选，总体积不超过 j，所有选法中的最大价值
从前 i 个硬币中选，总价值为 j，所有选法中所需硬币最少的个数
状态转移方程：
不选 i 硬币：dp[i][j] = dp[i – 1][j]
选 1 个 i 硬币：dp[i][j] = dp[i – 1][j – coins[i]] + 1（j >= coins[i]）
选 2 个 i 硬币：dp[i][j] = dp[i – 1][j – 2coins[i]] + 2（j >= 2coins[i]）
……………………
分析优化后：
dp[i][j] = min( dp[i – 1], dp[i][j – coins[i]] + 1 )（j >= coins[i]）
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<int>> dp(n+1,vector<int>(amount+1));
for(int j = 1; j <= amount; j++) dp[0][j] = 0x3f3f3f3f;//设一个无效值；因为状态转移方程是在取最小值，所以是0x3f3f3f3f而不是负的
for(int i = 1; i <= n; i++){
for(int j = 0; j <= amount; j++){
dp[i][j] = dp[i-1][j];
if(j >= coins[i-1]) //注意coins的下标
dp[i][j] = min(dp[i-1][j],dp[i][j - coins[i-1]] + 1);
}
}
return dp[n][amount] == 0x3f3f3f3f ? -1 : dp[n][amount];
}
};
空间优化略
例题49：零钱兑换 II
零钱兑换 II
class Solution {
public:
int change(int amount, vector<int>& coins) {
//dp[i][j]：从前 i 个硬币中选，总价值为 j，有多少种组合方式
//不选 i：dp[i][j] = dp[i-1][j]
//选一个 i：dp[i][j] += dp[i-1][j-coins[i]]（j >= coins[i]）
//…………………………
//dp[i][j] = dp[i-1][j] (+ dp[i][j-coins[i]])
int n = coins.size();
vector<vector<int>> dp(n+1,vector<int>(amount+1));
dp[0][0] = 1;//含义：不选硬币总金额为0，是一种方法
for(int i = 1; i <= n; i++){
for(int j = 0; j <= amount; j++){
dp[i][j] += dp[i-1][j];
if(j >= coins[i-1]) //注意coins的下标
dp[i][j] += dp[i][j-coins[i-1]];
}
}
return dp[n][amount];
}
};
例题50：完全平方数
完全平方数
class Solution {
public:
int numSquares(int n) {
const int INT = 0x3f3f3f3f;
int num = sqrt(n);//★
vector<vector<int>> dp(num+1,vector<int>(n+1));
for(int j = 1; j <= n; j++) dp[0][j] = INT;
for(int i = 1; i <= num; i++){
for(int j = 0; j <= n; j++){
dp[i][j] = dp[i-1][j];
if(j >= i*i) dp[i][j] = min(dp[i-1][j], dp[i][j-i*i] + 1);
}
}
return dp[num][n];
}
};
十、二维费用的背包问题
例题51：一和零 ★
一和零
此前的背包问题，都只有一个条件的限制，即背包的体积
而这道题却有两个限制，称为二维费用的背包问题
二维费用的背包问题也分（二维费用的） 01背包问题 和 完全背包问题
这道题显然是 二维费用的01背包问题
状态表示：
dp[i][j][k]：从前 i 个字符串中挑选，字符 0 的个数不超过 j，字符 1 的个数不超过 k，所有选法中字符串最多的个数
状态转移方程：
不选 i：dp[i][j][k] = dp[i – 1][j][k]
选 i（设 i 字符串中有 a 个 0，b 个 1，若 j >= a 且 k >= b）：
dp[i][j][k] = dp[i – 1][j – a][k – b] + 1
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int num = strs.size();
vector<vector<vector<int>>> dp(num+1,vector<vector<int>>(m+1,vector<int>(n+1)));
for(int i = 1; i <= num; i++){
//统计该字符串i中 0 1 的个数
int a = 0, b = 0;
for(auto ch : strs[i-1]){
if(ch == '0') a++;
else b++;
}
for(int j = 0; j <= m; j++){
for(int k = 0; k <= n; k++){
dp[i][j][k] = dp[i-1][j][k];
if(j >= a && k >= b)
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-a][k-b] + 1);
}
}
}
return dp[num][m][n];
}
};
空间优化（01背包问题需要注意优化后从大往小遍历）
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int num = strs.size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i = 1; i <= num; i++){
//统计该字符串i中 0 1 的个数
int a = 0, b = 0;
for(auto ch : strs[i-1]){
if(ch == '0') a++;
else b++;
}
for(int j = m; j >= a; j--){
for(int k = n; k >= b; k--){
dp[j][k] = max(dp[j][k], dp[j-a][k-b] + 1);
}
}
}
return dp[m][n];
}
};
例题52：盈利计划
盈利计划
出题者语言组织多少有点问题，说的云里雾里的
状态表示：
dp[i][j][k]：从前 i 个工作中挑选，总人数不超过 j，总利润至少为 k，一共有多少种选法
状态转移方程：
（不选 i 计划）dp[i][j][k] += dp[i – 1][j][k]
（选 i 计划）dp[i][j][k] += dp[i – 1][j – group[i]][max(0, k – profit[i])]（j >= group[i]）
解释：j – group[i] 好说，max(0, k – profit(i)) 是什么东西？
我们知道，j – group[i] 是不可以小于 0 的 —— 做了 i 工作后倒欠了几个人
但 k – profit(i) 是可以小于 0 的 —— i 工作的利润超高，需要达成的利润成了负数，前面的工作做不做都无所谓了；但是，尽管这里小于零具有意义，但我们数组下标不能小于 0，所以当 k – profit(i) < 0 时我们可以用 0 来代替这种情况（毕竟所需利润为负和为0，效果上是一样的）
初始化：
dp[0][j][k]：若 k != 0，没有计划能选却要产生利润 —— 不可能，0 种选法（不过似乎没有推导的必要，和之前的题一样，因为有 j >= group[i] 和 max(0, k – profit[i] 的判断，放心地把这部分放进循环里一块计算就行了）
dp[0][j][0]：只有人，没有计划，不要求利润 —— 什么都不做，1 种选法
class Solution {
public:
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
const int MOD = 1e9 + 7;
int len = group.size();//len个工作，n个人，minProfit的利润
vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(n+1,vector<int>(minProfit+1)));
for(int j = 0; j <= n; j++) dp[0][j][0] = 1;
for(int i = 1; i <= len; i++){
for(int j = 0; j <= n; j++){
for(int k = 0; k <= minProfit; k++){
dp[i][j][k] = dp[i - 1][j][k];
if(j >= group[i-1])
dp[i][j][k] += dp[i - 1][j - group[i-1]][max(0, k - profit[i-1])];//注意下标
dp[i][j][k] %= MOD;
}
}
}
return dp[len][n][minProfit];
}
};
十一、似包非包
例题53：组合总和 Ⅳ
组合总和 Ⅳ
长得像背包问题，但我们此前做的背包问题都是 “ 组合 ”，而这个问题它名字叫组合，实则是排序
那就是时候用到 确定状态表示的方法3：在分析问题的过程中发现重复子问题 了
说来不觉得这道题和作为引子的凑零钱问题神似吗
分析：目标 target，nums[i] 可供选择，有多少种方式？
若选择 nums[0]、nums[1]、nums[2] ……
问题就变成了一堆子问题：目标 target – nums[0]、target – nums[1]、target – nums[1] ……，nums[i] 可供选择，一共有多少种方式？
重复子问题
除了不用取最小，和凑零钱简直如出一辙
状态表示：
dp[i]：从 nums 数组中选择数据，目标为 i，一共的方法数
状态转移方程：
dp[i] += dp[i – nums[0 ~ x]]（i >= x）
初始化：
增加一个虚拟位置，dp[0] = 1（含义：目标为0，不选即可 —— 一种方法）
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<double> dp(target+1);//这道题不讲武德，即便用long long计算过程中也会超出范围
dp[0] = 1;
for(int i = 1; i <= target; i++){
for(auto x : nums){
if(i >= x) dp[i] += dp[i - x];
}
}
return dp[target];
}
};
十二、卡特兰数
例题54：不同的二叉搜索树 ★
不同的二叉搜索树
分析：将数字 1~n（n个数） 存入搜索二叉树中，可以得到多少种不同的二叉树
若根节点为 j，其左树范围 [1, j – 1]（j – 1个数） ，右树范围 [j + 1, n]（n – j 个数）
于是问题就变成了：将数字 1 ~ j – 1（j – 1个数）/ j + 1 ~ n（ n – j 个数） 存入搜索二叉树中，可以得到多少种不同的二叉树
状态表示：
dp[i]：将 i 个数存入搜索二叉树中，可以得到多少种不同的二叉树
状态转移方程：
dp[i] += dp[j-1] * dp[i-j]（1 <= j <= i）
这个状态转移方程叫做卡特兰数
初始化：
增加一个虚拟位置，dp[0] = 1（空树也是一个数……感觉好牵强……但结合后面填表的情况，这里应当是 1）
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[i-j] * dp[j-1];
return dp[n];
}
};
版权声明：本文为博主作者：小博XB原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/2201_75352211/article/details/136131215
