目录
1. 解决动态规划的基本思路
一维dp例题
1. 爬楼梯(力扣70)
2. 整数划分问题
解题步骤:
3.非连续子数组和(该题与力扣198题打家劫舍相似)
解题步骤:
力扣198打家劫舍
4. 最大子数组和(力扣53)
分析:
代码:
二维dp例题
1. 01背包
代码:
2. 最长公共子序列(力扣1143)
代码:
3. 最长重复子数组(力扣718)
代码:
4. 编辑距离(力扣72)
代码
5. 完全背包
分析:
代码:
1. 解决动态规划的基本思路
动态规划:通过子问题的求解得到最终问题的答案
1. 定义问题:即定义dp数组。明确dp数组的含义
2. 分解问题:一般是根据题意得到递推式
3. 解决子问题:根据dp数组的定义求出边界条件,即dp数组的初始化操作
一维dp例题
1. 爬楼梯(力扣70)
1. 定义dp数组:
dp[i]:为爬到i级的种类是dp[i]
2. 分解(向前递推:考虑最后一步如何决策)
考虑最后一阶楼梯怎么爬(最后一步的决策)
如爬到第6阶的种类可由第五阶向上爬一阶,也可以从第四阶爬两阶
即 dp[i] = dp[i - 1] + dp[i - 2]
3. 解决子问题(不能继续分解的子问题)
如此题中 dp[1] = 1 dp[2] = 2
class Solution {
public:
int climbStairs(int n) {
if(n == 1) return n;
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
2. 整数划分问题
将一个整数用1,3,4进行划分,问有多少种情况?
例如:5 = 1 + 1 + 1 + 1 + 1
= 1 + 1 + 3
= 1 + 3 + 1
= 3 + 1 + 1
= 4 + 1
= 1 + 4 共六种
解题步骤:
1. 定义dp数组:
dp[i]:将i划分,共有dp[i]种
2. 分解(向前递推:考虑最后一步如何决策)
**考虑最后一个数字选 1,3还是 4**(最后一步的决策)
i可分解为 x1 + x2 + x3 + …… + xk
如果xk = 1, 则 dp[i] = dp[i -1]
如果xk = 3, 则 dp[i] = dp[i -3]
如果xk = 4, 则 dp[i] = dp[i -4]
得:dp[i] = dp[i -1] + dp[i -3] + dp[i -4]。一定要明确dp数组的含义
3. 解决子问题(不能继续分解的子问题)
如此题中 dp[1] = 1 dp[2] = 1 dp[3] = 2 dp[4] = 4
3.非连续子数组和(该题与力扣198题打家劫舍相似)
eg:a[] = {3 5 7 6 2 4} 求最大子数组和(禁用相邻元素)
选3不选5,选5不选3和7。以此类推
解题步骤:
1. 定义dp数组:
dp[i]为 [a[0], a[i]] 区间内的最大子数组和。如上例中便是求 d[5]
2. 分解(向前递推:考虑最后一步如何决策)
**考虑最后一个元素a[i]用还是不用**(最后一步的决策)
1. 不用最后一个元素a[i]:dp[i] = dp[i -1];
2. 用最后一个元素a[i]:dp[i] = dp[i -2] + a[i];
故递推方程为:dp[i] = max(d[i -1], dp[i -2] + a[i]);
3. 子问题
dp[0] = max(0, a[0]);
dp[1] = max(a[1], dp[0]);
力扣198打家劫舍
1. 定义问题:
dp[i] 表示前 i 间房屋能偷窃到的最高总金额
最终目标:求dp[len]
2. 分解问题(向前递推:考虑最后一步如何决策)
考虑第i家偷不偷(最后一步的决策)
1.如果偷第i家: dp[i] = dp[i -2] + a[i -1]
2.如果不偷第i家:dp[i] = dp[i -1]
故递推方程为:dp[i] = max(dp[i-1], dp[i -2] + a[i -1])
3. 解决子问题(根据dp数组的定义)
dp[0] = 0
dp[1] = a[0]
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
vector<int> dp(len +1, 0);
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i <= len; i++){
dp[i] = max(dp[i -1], dp[i -2] + nums[i -1]);
}
return dp[len];
}
};
4. 最大子数组和(力扣53)
该题与第三题的区别:第三题是有后效性的,该题是没有后效性的。
当你对第三题的问题进行分解时,第一个子问题的答案一般与第二个子问题的答案有明显的联系。只要知道递推式,然后求得dp数组的最终结果就能得到答案。而对于该题这种无后效性的问题,一般求解的是dp数组的max值。后面二维dp中也有类似的题目
分析:
1. 定义问题
dp[i]:以a[i]结尾的 [a[0], a[i]] 区间内最大子数组的和为 dp[i]
2. 分解问题
因为必须以a[i]结尾,故可得递推方程 dp[i] = dp[i -1] + a[i]。
考虑 dp[i -1]的符号及其定义,有以下两种情况发生
1. 当dp[i - 1] <=0 时,递推方程为:dp[i] = a[i]
2. 当dp[i -1] > 0 时,递推方程为:dp[i] = dp[i -1] + a[i];
3. 因为求的是最大连续子数组和,所以最后取值为 max(所有的dp[i][j]) 。dp数组中的最大值
3. 解决子问题
dp[0] = a[0]
代码:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
vector<int> dp(len, 0);
dp[0] = nums[0];
int max = dp[0];
for(int i = 1; i < len; i++){
if(dp[i -1] < 0){
dp[i] = nums[i];
}else{
dp[i] = dp[i -1]+ nums[i];
}
if(dp[i] > max) max = dp[i];
}
return max;
}
};
二维dp例题
1. 01背包
- 01背包:n种物品,每个物品只有一个,放入一个容量为C的背包,求最大价值
- 完全背包:n种物品,每个物品有无限个,放入一个容量为C的背包,求最大价值
- 多重背包:n种物品,每个物品个数各不相同,放入一个容量为C的背包,求最大价值
1. 定义dp数组:
dp[i][j]:前 i 件商品,放入容量为 j 的背包 的最大价值为 dp[i][j]
eg:求解dp[4][8] //将前4件商品,放入容量为8的背包所得最大价值为 dp[4][8]
2. 分解(向前递推:考虑最后一步如何决策)
i件商品: [0][1][2]……[i-2][i-1]
考虑第 i 件商品 是否放入背包(最后一步的决策)
eg:
dp[4][8] = max(dp[3][8], 6 + dp[3][3]) // 第4件商品的价值为6,容量为5
将前 4 件商品放入容量为8的背包最大价值:
1. 第四件商品不放入,即前三件商品放入容量为8的背包的最大价值
2. 第四件商品放入,将前三件商品放入容量为 3 的背包
的最大价值 + 第四件商品的价值
得递推方程 dp[i][j] = max(dp[i - 1][j], v[i -1] + dp[i-1][j - w[i -1])
3. 解决子问题(不能继续分解的子问题)
dp[0][0] = 0 0物品放入0容量背包
dp[i][0] = 0 前i件物品放入容量为0背包
dp[0][j] = 0 0物品放入容量为i的背包
代码:
#include <bits/stdc++.h>
using namespace std;
int M, N; //M:物品种类,N:背包容量
void solve(){
vector<int> weight(M, 0); //每件物品所占空间
vector<int> value(M, 0); //每件物品的价值
//每件物品的价值,所占空间 初始化
for(int i = 0; i < M; i++) cin >> weight[i];
for(int i = 0; i < M; i++) cin >> value[i];
//二维dp数组的定义:
// dp[i][j]:前i件物品,放入容量为j的背包,所得到的最大价值为dp[i][j]
vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
//这里初始化可以省略,因为在定义dp数组时所有的元素都是0
//for(int i = 0; i <= M; i++) dp[i][0] = 0;
//for(int j = 0; j <= N; j++) dp[0][j] = 0;
for(int i = 1; i <= M; i++){
for(int j = 1; j <= N; j++){
if(weight[i -1] > j){ //第i件物品所占空间比背包空间还大,则第i件物品不放入背包
dp[i][j] = dp[i -1][j];
}else{
dp[i][j] = max(dp[i -1][j], value[i -1] + dp[i -1][j - weight[i -1]]);
}
}
}
cout << dp[M][N] << endl;
}
int main(){
cin >> M >> N;
solve();
return 0;
}
2. 最长公共子序列(力扣1143)
跟一维dp中的第3题类似
1. 定义dp数组
dp[i][j] :s1前i个字符与s2前j个字符的最长公共子序列长度为 dp[i][j].
最终目标:dp[m][n]
2. 分解问题(向前递推:考虑最后一步如何决策)
**考虑s1中第i个元素是否与s2中第j个元素相同**(最后一步的决策)
1. 如果相同,即 s1[i -1] == s2[j -1], 则 dp[i][j] = dp[i -1][j -1] + 1
2. 如果不相同,则考虑 s1 的前 i -1 个字母 和 s2 的 前 j个字母比较,以及 s1 的前 i 个字母和s2的前j -1个字母比较,取其中的较大者。 即 dp[i][j] = max(dp[i -1][j], dp[i][j -1])
3. 子问题(根据dp数组的定义)
dp[0][0] = 0
dp[i][0] = 0
dp[0][j] = 0
代码:
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> dp(m +1, vector<int>(n +1, 0));
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
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]);
}
}
}
return dp[m][n];
}
};
3. 最长重复子数组(力扣718)
该问题同一维dp中的第4题相似,是一个无后效性问题,需求dp数组的max值
1. 定义问题
dp[i][j]:nums1中以i结尾的前i项 和 nums2中以j结尾的前j项 最长连续公共子数组的长度为dp[i][j]
2. 分解问题
**考虑nums1中第i个元素是否与nums2中第j个元素相同**
1. 相同,则不难推出 dp[i][j] = dp[i -1][j -1] + 1
2. 不同,dp[i][j] = 0【求的是 nums1中以i结尾的前i项 和 nums2中以j结尾的前j项最长相等后缀,但后缀的第一个元素就不相等】
3. 因为求的是最长相等后缀,所以最后取值为 max(所有的dp[i][j]) 。dp数组中的最大值
3. 解决子问题
dp[0][0] = 0
dp[i][0] = 0
dp[0][j] = 0
代码:
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
vector<vector<int>> dp(m +1, vector<int>(n +1, 0));
int max = 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;
}
if(dp[i][j] > max) max = dp[i][j];
}
}
return max;
}
};
4. 编辑距离(力扣72)
1. 定义dp数组
dp[i][j]:s1前i个字符转化为s2的前j个字符需要的最少的操作数为dp[i][j], 如将 sun 转换成satur需要最少3次操作,故 dp[3][5] = 3。最终目标是求:dp[m][n]
2. 分解问题
1. s1 和 s2 末尾字符相同,则无需考虑最后一个字符的转换。
即当 s1[i -1] == s2[j -1]时, dp[i][j] = dp[i -1][j -1]
2. s1 和 s2 末尾字符不相同时,对s1进行插入,删除,替换操作
(题意是将s1转换为s2,所以下面所有操作都是对s1进行操作)
1.若进行插入操作,即s1[i] = s2[j -1] 则默认 s1前 i 项 与 s2 前 j -1 项高度重合。dp[i][j] = dp[i][j -1] + 1
2.若进行删除操作,即s1[i -1] = NULL, 则默认 s1前 i -1项与 s2前
j 项高度重合。dp[i][j] = dp[i-1][j] + 1
3. 若进行替换操作,即 s1[i-1] = s2[j -1], 则默认 s1前i -1项 与s2
前 j -1项高度重合。dp[i][j] = dp[i-1][j-1] + 1
故dp[i][j] = min( dp[i][j -1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1);
3. 解决子问题
通过dp数组定义来确定子问题的解
dp[0][0] = 0;
dp[i][0] = i; // 将s1 的前i个字符转换为s2 的前0个字符。即将s1的前i个字符删除
dp[0][j] = j; //将s1插入j次得到s2
代码
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m +1, vector<int>(n +1, 0));
for(int i = 0; i <= m ; i++) dp[i][0] = i;
for(int j = 0; j <= n; j++) dp[0][j] = j;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(word1[i -1] == word2[j -1]){ // w1的第i个字符和w2的第j个字符相同
dp[i][j] = dp[i -1][j -1];
}else{
dp[i][j] = min(min(dp[i -1][j] +1, dp[i][j -1] +1), dp[i -1][j -1] +1);
}
}
}
return dp[m][n];
}
};
5. 完全背包
n种物品,每个物品有无限个,放入一个容量为C的背包,求最大价值。
完全背包是基于01背包扩展而来。可以看完01背包再来看这个。
完全背包和01背包最大的区别就是完全背包可以放入多件同种物品。表现在dp数组中有如下区别,详细讲解见下面的分析:
01背包:dp[i][j] = max(dp[i - 1][j], v[i -1] + dp[i-1][j - w[i -1])
完全背包:dp[i][j] = max(dp[i - 1][j], v[i -1] + dp[i][j - w[i -1])
分析:
1. 定义dp数组:
dp[i][j]:前 i 件商品,放入容量为 j 的背包 的最大价值为 dp[i][j]
eg:求解dp[4][16]
2. 分解(向前递推:考虑最后一步如何决策)
eg:
dp[4][16] = max(dp[3][16], 6 + dp[4][11]) // 第4件商品的价值为6,容量为5
将前 4 件商品放入容量为16的背包最大价值:
1. 第四件商品不放入,即前三件商品放入容量为16的背包的最大价值
2. 第四件商品放入,如果背包中剩余的空间还能放入第四件商品,继续将前四件商品放入容量为 11 的背包的最大价值 + 第四件商品的价值
i件商品: [0][1][2]……[i-2][i-1]
考虑第 i 件商品 是否放入背包(最后一步的决策)
- 第i件物品不放入,则 dp[i][j] = dp[i -1][j]
- 第i件物品放入,由于该物品有无限个,考虑背包剩余的空间能否继续放第i件物品,如果能继续放第i件物品,则 dp[i][j] = dp[i][j -w[i -1]] + v[i -1]
注:对于第二步,本质还是将其当成01背包去处理,每次只放一件物品
得递推方程 dp[i][j] = max(dp[i - 1][j], v[i -1] + dp[i][j - w[i -1]])
3. 解决子问题(不能继续分解的子问题)
dp[0][0] = 0 0物品放入0容量背包
dp[i][0] = 0 前i件物品放入容量为0背包
dp[0][j] = 0 0物品放入容量为i的背包
代码:
#include <bits/stdc++.h>
using namespace std;
int M, N; //M:物品种类,N:背包容量
void solve(){
vector<int> weight(M, 0); //每件物品所占空间
vector<int> value(M, 0); //每件物品的价值
//每件物品的价值,所占空间 初始化
for(int i = 0; i < M; i++) cin >> weight[i] >> value[i];
//二维dp数组的定义:
// dp[i][j]:前i件物品,放入容量为j的背包,所得到的最大价值为dp[i][j]
vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
//这里初始化可以省略,因为在定义dp数组时所有的元素都是0
//for(int i = 0; i <= M; i++) dp[i][0] = 0;
//for(int j = 0; j <= N; j++) dp[0][j] = 0;
for(int i = 1; i <= M; i++){
for(int j = 1; j <= N; j++){
if(weight[i -1] > j){ //第i件物品所占空间比背包空间还大,则第i件物品不放入背包
dp[i][j] = dp[i -1][j];
}else{
dp[i][j] = max(dp[i -1][j], value[i -1] + dp[i][j - weight[i -1]]);
}
}
}
cout << dp[M][N] << endl;
}
int main(){
cin >> M >> N;
solve();
return 0;
}
6. 多重背包
n种物品,每个物品个数各不相同,放入一个容量为C的背包,求最大价值
例:
有M种物品和一个容量为C 的背包。第i种物品最多有Mi件,每件耗费的空间是Wi ,价值是Vi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量,且价值总和最大。
同完全背包,本质是将其转为01背包。文章来源:https://www.toymoban.com/news/detail-751899.html
故需要添加一个数组count记录每件物品的个数,当添加第i个物品时,第i个物品的取值范围是[1, Mi],从其中找一个符合条件的最大值k,表示前k件第i个物品能放进背包的剩余空间,而第 k+1件第i个物品不能放进背包的剩余空间文章来源地址https://www.toymoban.com/news/detail-751899.html
代码
#include <bits/stdc++.h>
using namespace std;
int M, N; //M:物品种类,N:背包容量
void solve(){
vector<int> weight(M, 0); //每件物品所占空间
vector<int> value(M, 0); //每件物品的价值
vector<int> count(M, 0); // 每件物品的个数
//每件物品的 所占空间,价值,个数 初始化
for(int i = 0; i < M; i++) cin >> weight[i];
for(int i = 0; i < M; i++) cin >> value[i];
for(int i = 0; i < M; i++) cin >> count[i];
//二维dp数组的定义:
// dp[i][j]:前i件物品,放入容量为j的背包,所得到的最大价值为dp[i][j]
vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
//这里初始化可以省略,因为在定义dp数组时所有的元素都是0
//for(int i = 0; i <= M; i++) dp[i][0] = 0;
//for(int j = 0; j <= N; j++) dp[0][j] = 0;
for(int i = 1; i <= M; i++){
for(int j = 1; j <= N; j++){
dp[i][j] = dp[i -1][j]; // 不放第i个物品
// 放k件第i个物品;直到k件第i个物品所占空间大于背包剩余容量,则不再继续放第 k+1件第i个物品
for(int k = 1; k <= count[i -1] && k * weight[i -1] <= j; k++){
dp[i][j] = max(dp[i][j], k * value[i -1] + dp[i -1][j - k * weight[i -1]]);
}
}
}
cout << dp[M][N] << endl;
}
int main(){
cin >> N >> M;
solve();
return 0;
}
到了这里,关于动态规划基础的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!