🍋前言：
🌵🌵蓝桥杯就剩一天了，祝看到这篇文章的老铁们都有好成绩~
🌴🌴这里总结了一些动态规划的常见模型，最后一天拿来复习一波，万一中了呢🤣
🍍1.最大子段和
- 最大子段和或者叫最大子数组和。
- f(i)代表以第 i个数结尾的「连续子数组的最大和」，对数组中的任意一个位置 n u m s [ i ] nums[i] nums[i]，要么单独作为一个子段，要么和前面的子段合并,状态转移方程： f ( i ) = m a x ( f ( i − 1 ) + n u m s [ i ] , n u m s [ i ] ) f(i)=max{(f(i−1)+nums[i],nums[i])} f(i)=max(f(i−1)+nums[i],nums[i])。
🚀题目链接：LeetCode53.最大子数组和
🍦参考代码（Java）：
classSolution{publicintmaxSubArray(int[] nums){int len = nums.length;int[] dp =newint[len];
dp[0]= nums[0];int max = dp[0];for(int i =1; i < len; i++){
dp[i]= nums[i]+Math.max(dp[i -1],0);
max =Math.max(max, dp[i]);}return max;}}
🍓2.最长递增子序列
🚀题目链接：LeetCode300.最长递增子序列
- 最长递增子序列Longest Increasing Subsequence，即LIS。
d p [ i ] dp[i] dp[i]表示选择 n u m s [ i ] nums[i] nums[i]，并且以 n u m s [ i ] nums[i] nums[i]结尾的最长上升子序列的长度。- 需要双层循环
for i = 1 ~ nums.length，for j = 0 ~ i，如果 n u m s [ i ] > n u m s [ j ] nums[i] > nums[j] nums[i]>nums[j]，说明构成了一个递增对，状态转移： d p [ i ] = m a x ( d p [ i ] , d p [ j ] + 1 ) dp[i] = max{(dp[i], dp[j] + 1)} dp[i]=max(dp[i],dp[j]+1)，最后返回 d p dp dp数组中的最大值即为答案。
🍦参考代码（Java）：
classSolution{publicintlengthOfLIS(int[] nums){int n = nums.length;int[] dp =newint[n];Arrays.fill(dp,1);//base case : dp[0] = 1;for(int i =1;i < n; i++){for(int j =0; j < i; j++){if(nums[j]< nums[i])
dp[i]=Math.max(dp[j]+1,dp[i]);}}int ans =0;for(int i =0; i < n;i++)
ans =Math.max(ans,dp[i]);return ans;}}
🍊3.最长公共子序列
🚀题目链接：LeetCode1143.最长公共子序列
- 最长公共子序列 Longest Common Subsequence，即LCS。
- 题目涉及两个字符串，使用二维
dp[][]，dp[i][j]表示第一个字符串的0~i前缀子串与第二个字符串的0~j前缀子串的最长公共子序列。 - 若第一个字符串的i位置与第二个字符串的j位置的两个字符相等，则 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i - 1][j - 1] + 1 dp[i][j]=dp[i−1][j−1]+1，若两个位置的字符不等则 d p [ i ] [ j ] dp[i][j] dp[i][j]取 d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i−1][j]与 d p [ i ] [ j − 1 ] dp[i][j - 1] dp[i][j−1]的最大值。
- 状态转移方程：
🍦参考代码（Java）：
classSolution{publicintlongestCommonSubsequence(String text1,String text2){int len1 = text1.length();int len2 = text2.length();int[][] dp =newint[len1+1][len2+1];for(int i =1; i <= len1; i++){for(int j =1; j <= len2; j++){if(text1.charAt(i-1)== text2.charAt(j-1))
dp[i][j]= dp[i-1][j-1]+1;else
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}return dp[len1][len2];}}
🍈4.编辑距离
🚀题目链接：LeetCode72.编辑距离
- 题目涉及两个字符串，使用二维
dp[][]。 d p [ i ] [ j ] dp[i][j] dp[i][j]表示```word1```的前```i```个字母转换成```word2```的前```j```个字母所使用的最少操作。- 若 w o r d [ i ] = w o r d [ j ] word[i] = word[j] word[i]=word[j]，状态转移： d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j] = dp[i - 1][j - 1] dp[i][j]=dp[i−1][j−1]。
- 若 w o r d [ i ] ≠ w o r d [ j ] word[i] \not= word[j] word[i]=word[j]，说明当前位置需要一次修改，再加上之前需要修改的次数，则状态转移： d p [ i ] [ j ] = m i n ( d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] ) + 1 dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1 dp[i][j]=min(dp[i][j−1],dp[i−1][j],dp[i−1][j−1])+1
🍦参考代码（Java）：
classSolution{publicintminDistance(String word1,String word2){int len1 = word1.length();int len2 = word2.length();int[][] dp =newint[len1+1][len2+1];for(int i =1; i <= len1; i++)
dp[i][0]= i;for(int i =1; i <= len2; i++)
dp[0][i]= i;for(int i =1; i <= len1; i++){for(int j =1; j <= len2; j++){if(word1.charAt(i-1)== word2.charAt(j-1))
dp[i][j]= dp[i-1][j-1];else
dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;}}return dp[len1][len2];}}
🍑5. 01背包问题
🚀题目链接：https://oj.czos.cn/p/1282
题目描述
有一个背包能装的重量maxw(正整数，0≤maxw≤20000)，同时有n件物品(0≤n≤100)，每件物品有一个重量wi(正整数)和一个价值pi(正整数)。要求从这n件物品中任取若干件装入背包内，使背包的物品价值最大。
输入
第1行：背包最大载重maxw，物品总数n
第2行到第n+1行：每个物品的重量和价值输出
一个数字即背包内物品最大价值
样例：
输入
10 3 4 5 3 4 6 9输出
14
- 二维
dp[][]，dp[i][j]对于前i个物品，放在背包，重量不超过j的前提下，所获得的最大价值为dp[i][j]。 - 当第
i个物品的重量大于j，说明放不进去，状态转移： d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i - 1][j] dp[i][j]=dp[i−1][j]。 - 当第
i个物品的重量小于j，说明可以装包，设第i个物品的重量为 c i c_i ci，重量 w i w_i wi，状态转移： d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c i ] + w i ） dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - c_i] + w_i） dp[i][j]=max(dp[i−1][j],dp[i−1][j−ci]+wi）。
🍦参考代码（Java）：
importjava.util.Scanner;publicclassMain{publicstaticint n;publicstaticint maxw;publicstaticint[] w =newint[105];publicstaticint[] p =newint[105];publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);
maxw = sc.nextInt();
n = sc.nextInt();for(int i =1; i <= n; i++){
w[i]= sc.nextInt();
p[i]= sc.nextInt();}int[][] dp =newint[n +1][maxw +1];for(int i =1; i <= n; i++){for(int j =0; j <= maxw; j++){if(w[i]> j){
dp[i][j]= dp[i -1][j];}else{
dp[i][j]=Math.max(dp[i -1][j], dp[i -1][j - w[i]]+ p[i]);}}}System.out.println(dp[n][maxw]);
sc.close();}}
🍸01背包优化（状态压缩）：
- 由状态转移方程不难发现，对于
dp[i][...]只和它的上一行dp[i - 1][...]有关系，可以在空间上做一下优化。 - 可以使用一个一维数组滚动记录
dp[i][...]的上一行数据。 - 在一维数组上要从后向前推导，不然
dp[i][j]的值会被覆盖掉，向后推会出错。 - 状态转移返程为： d p [ j ] = m a x ( d p [ j ] , p [ i ] + d p [ j − w [ i ] ] ) dp[j] = max(dp[j],p[i] + dp[j - w[i]]) dp[j]=max(dp[j],p[i]+dp[j−w[i]])
🍦参考代码（Java）：
importjava.util.Scanner;publicclassMain{publicstaticint n;publicstaticint maxw;publicstaticint[] w =newint[105];publicstaticint[] p =newint[105];publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);
maxw = sc.nextInt();
n = sc.nextInt();for(int i =1; i <= n; i++){
w[i]= sc.nextInt();
p[i]= sc.nextInt();}int[] dp =newint[maxw +1];for(int i =1; i <= n; i++){for(int j = maxw; j >= w[i]; j--){
dp[j]=Math.max(dp[j], dp[j - w[i]]+ p[i]);}}System.out.println(dp[maxw]);
sc.close();}}
🍐6.多重背包问题
🚀题目链接：https://oj.czos.cn/p/1888
题目描述
有
N N N种物品和一个容量是 V V V的背包。第i种物品最多有
S i S_i Si件，每件体积是 V i V_i Vi，价值是 W i W_i Wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。输入
第一行两个整数，
N N N， V V V，用空格隔开，分别表示物品种数和背包容积。接下来有
N N N 行，每行三个整数 v i , w i , s i v_i,w_i,s_i vi,wi,si，用空格隔开，分别表示第i种物品的体积、价值和数量。
0 < N , V ≤ 100 0<N,V≤100 0<N,V≤100 0 < v i , w i , s i ≤ 100 0<v_i,w_i,s_i≤100 0<vi,wi,si≤100输出
输出一个整数，代表最大价值。
样例
输入
4 10 3 2 2 4 3 2 2 2 1 5 3 4输出
8
- 将多重背包转换为01背包。
- 将 S i S_i Si件物品都存起来，转换为有 S i S_i Si个物品，每个物品有一件。
- 这里并不需要改变
dp[][]数组的长度从而真的将物品拆分成一件，只需要在01背包的基础上加一层循环即可。
🍦参考代码（Java）：
importjava.util.Scanner;publicclassMain{publicstaticint n;publicstaticint v;publicstaticint[] v_i =newint[105];publicstaticint[] w_i =newint[105];publicstaticint[] s_i =newint[105];publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);
n = sc.nextInt();
v = sc.nextInt();for(int i =1; i <= n; i++){
v_i[i]= sc.nextInt();
w_i[i]= sc.nextInt();
s_i[i]= sc.nextInt();}int[] dp =newint[v +1];for(int i =1; i <= n; i++){for(int k =1; k <= s_i[i]; k++){for(int j = v; j >= v_i[i]; j--){
dp[j]=Math.max(dp[j], dp[j - v_i[i]]+ w_i[i]);}}}System.out.println(dp[v]);}}
🍏7.完全背包问题
🚀题目链接：https://oj.czos.cn/p/1780
题目描述
仙岛上种了无数的不同种类的灵芝，小芳跟着爷爷来到仙岛采摘灵芝。由于他们带的食物和饮用水有限，必须在时间t内完成采摘。
假设岛上有m种不同种类的灵芝，每种灵芝都有无限多个，已知每种灵芝采摘需要的时间，以及这种灵芝的价值；
请你编程帮助小芳计算，在有限的时间t内，能够采摘到的灵芝的最大价值是多少？输入
输入第一行有两个整数T（1 <= T <= 100000）和M（1 <= M <= 2000），用一个空格隔开，T代表总共能够用来采灵芝的时间，M代表岛上灵芝的种类数。接下来的M行每行包括两个在1到10000之间（包括1和10000）的整数，分别表示采摘某种灵芝的时间和这种灵芝的价值。
输出
输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的灵芝的最大总价值。
样例
输入
70 3 71 100 69 1 1 2输出
140
- 题目完全可以看成是背包问题，时间相当于背包问题的体积，不过与01背包的区别在于物品有无限个，这种背包叫做完全背包。
⭐回顾一下01背包：
- 设物品重量 w i w_i wi，价值 v i v_i vi,01背包的状态转移方程： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − w [ i ] ] + v [ i ] ) f[i][j] = max(f[i - 1][j],f[i - 1][j - w[i]] + v[i]) f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])。
- 转换为一维滚动数组的状态转移方程： f [ j ] = m a x ( f [ j ] , f [ j − w [ i ] ] + v [ i ] ) f[j] = max(f[j],f[j - w[i]] + v[i]) f[j]=max(f[j],f[j−w[i]]+v[i])。
⭐接下来试着推到完全背包的状态转移方程：
- 设物品件数为 k k k，可以想到完全背包的状态转移方程： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − k × w [ i ] ] + k × v [ i ] ) f[i][j] = max(f[i - 1][j],f[i - 1][j - k \times w[i]] + k \times v[i]) f[i][j]=max(f[i−1][j],f[i−1][j−k×w[i]]+k×v[i])，限制条件 1 < = k < = w / w [ i ] 1 <= k <= w/w[i] 1<=k<=w/w[i]，此时需要三重循环。
k = 0 k = 0 k=0代表不取第```i```件物品，转移方程化简为： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j − k × w [ i ] ] + k × v [ i ] ) f[i][j] = max(f[i - 1][j - k \times w[i]] + k \times v[i]) f[i][j]=max(f[i−1][j−k×w[i]]+k×v[i])。- 或者把 k = 0 k = 0 k=0的情况单独拿出来考虑，状态转移方程为： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , m a x ( f [ i − 1 ] [ j − k × w [ i ] ] + k × v [ i ] ) ) f[i][j] = max(f[i - 1][j],max(f[i - 1][j - k \times w[i]] + k \times v[i])) f[i][j]=max(f[i−1][j],max(f[i−1][j−k×w[i]]+k×v[i]))
- 考虑上式放第
i种物品的情况，放的话至少放一件，先把这一件放进去，状态转移方程变型为： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , m a x ( f [ i − 1 ] [ ( j − w [ i ] ) − k × w [ i ] ] + k × v [ i ] ) + v [ i ] ) f[i][j] = max(f[i - 1][j],max(f[i - 1][(j - w[i]) - k \times w[i]] + k \times v[i]) + v[i]) f[i][j]=max(f[i−1][j],max(f[i−1][(j−w[i])−k×w[i]]+k×v[i])+v[i]) - 将第 2 2 2步的式子中的
j换成j - w[i]得到： f [ i ] [ j − w [ i ] ] = m a x ( f [ i − 1 ] [ ( j − w [ i ] ) − k × w [ i ] ] + k × v [ i ] ) f[i][j - w[i]] = max(f[i - 1][(j - w[i]) - k \times w[i]] + k \times v[i]) f[i][j−w[i]]=max(f[i−1][(j−w[i])−k×w[i]]+k×v[i])，结合第 4 4 4步的式子得到： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − w [ i ] ] + v [ i ] ) f[i][j] = max(f[i - 1][j],f[i][j - w[i]] + v[i]) f[i][j]=max(f[i−1][j],f[i][j−w[i]]+v[i]) 发现 k k k已经被消掉了，只需要双重循环就可以解决问题，跟01背包的状态转移方程只有一处差别，f[i - 1][j - w[i]] + v[i]变为f[i][j - w[i]] + v[i]。
⭐完全背包的状态转移方程已经和01背包很像了，到了这里如何做一维数组滚动优化呢？
- 考虑到跟01背包状态转移方程的差别，计算第
i行时不需要保留第i - 1行的数据了，因此只需要从当前物品的重量 w i w_i wi正序循环至背包容量 c c c，状态转移方程完全不变。 d p [ j ] = m a x ( d p [ j ] , d p [ j − w [ i ] ] + v [ i ] ) dp[j] = max(dp[j],dp[j - w[i]] + v[i]) dp[j]=max(dp[j],dp[j−w[i]]+v[i])
🍦参考代码（Java）：
importjava.util.Scanner;publicclassMain{publicstaticint t;publicstaticint m;publicstaticint[] t_i =newint[2005];publicstaticint[] v_i =newint[2005];publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);
t = sc.nextInt();
m = sc.nextInt();for(int i =1; i <= m; i++){
t_i[i]= sc.nextInt();
v_i[i]= sc.nextInt();}int[] dp =newint[t +1];for(int i =1; i <= m; i++){for(int j = t_i[i]; j <= t; j++){
dp[j]=Math.max(dp[j], dp[j - t_i[i]]+ v_i[i]);}}System.out.println(dp[t]);}}
🍌🍌🍌
动态规划的常见模型+背包问题都在这里啦~
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。🙇🏻♀️
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲一枚，请大佬们多多关照~
本文转载自: https://blog.csdn.net/m0_51338272/article/details/124022896
版权归原作者 Mymel_晗 所有， 如有侵权，请联系我们删除。
版权归原作者 Mymel_晗 所有， 如有侵权，请联系我们删除。