动态规划 线性 DP 五大经典模型：LIS、LCS、合唱队形、编辑距离 详解与模板

文章目录

• 最长上升子序列
• 【模板】最长上升子序列
• 合唱队形
• 牛可乐和最长公共子序列
• 编辑距离

经典线性 dp 问题有两个：最⻓上升⼦序列（简称：LIS）以及最⻓公共⼦序列（简称：LCS），这两道题⽬的很多⽅⾯都是可以作为经验，运⽤到别的题⽬中。⽐如：解题思路，定义状态表⽰的⽅式，推到状态转移⽅程的技巧等等。
因此，这两道经典问题是需要我们重点掌握的。

最长上升子序列

题目描述

题目解析
本题介绍最长上升子序列的一般解法，当数据量不大时用这种解法。
在此之前，小编先区分一下子数组和子序列，子数组需要是连续的，而子序列可以是间断的。

1、状态表示
dp[i]表示以i结尾的所有子序列中，最长的上升子序列。
2、状态转移方程
还是以最后一步推导状态转移方程，分两种情况：
一、当序列长度为1时，因为dp[i]自己本身就是一个子序列，所以dp[i]的最小取值可能是1（比如总序列是一个递减序列的话，那么每个dp[i]的取值都会是1）
二、当序列长度大于1时，如果第i个格子前面的所有格子中有比第i个格子小的格子，记为j，那么第i个格子就可以挂在j格子后面组成一个序列，序列长度就是dp[j]加1，因为我们要求最长上升子序列，所以需要遍历dp数组中从1到i-1的所有值，找出所有a[j]小于a[i]的格子，从中选出dp[j] + 1的最大值，该值为dp[i]的取值。

所以状态转移方程如下图所示：

3、初始化
因为我们没遍历到一个格子都会先把dp[i]置为1，所以dp数组不用初始化，用默认值0即可。
4、填表顺序
从左往右
5、输出结果
结果为dp数组从1到n的所有取值的最大值。

代码

#include<iostream>#include<algorithm>usingnamespace std;constint N =5010;int n;int a[N], dp[N];intmain(){//处理输入 cin >> n;for(int i =1; i <= n; i++){ cin >> a[i];}//初始化//按序填表int ret =0;for(int i =1; i <= n; i++){ dp[i]=1;for(int j =1; j < i; j++){//选出dp数组中1到i-1所有格子的最大值，把最大值加一赋给dp[i]if(a[j]< a[i]){ dp[i]=max(dp[i], dp[j]+1);}} ret =max(ret, dp[i]);} cout << ret << endl;return0;}

【模板】最长上升子序列

题目描述

题目解析
本题介绍最长上升子序列的推广解法，当数据量较大时用这种解法。
这里会利用贪心加二分优化时间复杂度，但是需要注意，这种方式是有局限性的，它只能求出最长上升子序列的长度，而不能还原出整个最长上升子序列。

在研究最长上升子序列时，其实只用关心序列的长度和序列最后一个元素是谁，我们并不关心序列具体长什么样子，本题是求解思路就是基于此实现的。
1、状态表示
对于原序列来说，我们先找出所有长度刚好是 i 的上升子序列（比如 i=3 时，就是所有长度为 3 的上升子序列），然后把这些子序列的最后一个数都列出来，在这些数里找最小的那个，这个最小的数就是 dp [i]。
这里用最小值充当dp[i]是用到了贪心的思想：要让序列尽可能长，就要让序列末尾元素尽可能小，让序列后面能挂更多元素。
2、状态转移方程
除了dp数组，我们还需要用一个全局变量len来存储最长上升子序列的长度。
填dp数组时我们要遍历整个a数组，首先处理边界情况，当len为0（序列为空）或者a[i]比dp[len]大（a[i]比最长序列的末尾元素还大）时，直接把len++，然后把a[i]赋值给dp[len]。否则就是一般情况，也就是序列本身已经有元素了，并且a[i]的值小于最长序列的末尾元素，这时我们要更新dp数组，但是len保持不变，更新策略是在dp数组中二分查找所有大于等于a[i]的元素中，其中的最小值所在的位置，然后把a[i]的值赋给该位置。（本质就是维护dp数组的特性：dp [i]为长度为i的所有子序列末尾元素的最小值）
3、初始化
无
4、填表顺序
从左往右
5、输出结果
len
代码

#include<iostream>usingnamespace std;constint N =1e5+10;int n;int a[N], dp[N];int len;//记录最长上升子序列长度intmain(){//处理输入 cin >> n;for(int i =1; i <= n; i++){ cin >> a[i];}//遍历原数组并填dp数组for(int i =1; i <= n; i++){if(len ==0|| a[i]> dp[len]){//边界情况，len和a[i]大于最长合法序列的末尾元素时//直接把a[i]放在dp数组++len处 dp[++len]= a[i];}//在dp数组中二分查找大于等于a[i]的最小值int l =1, r = len;while(l < r){int mid =(l + r)/2;if(dp[mid]>= a[i]){//答案在左半部分，包含mid r = mid;}else l = mid +1;}//把a[i]赋值给查找到的dp数组中大于等于a[i]的最小值 dp[l]= a[i];} cout << len;return0;}

合唱队形

题目描述

题目解析
本题是最长上升子序列问题的一个模板题，比较简单小编就简单说明一下。
依据题意，要找一个最长的先递增在递减的子序列，要让该子序列最长，就要分别让递增序列和递减序列都尽可能长，最终答案就是遍历所有同学找到一个同学i，以他为顶峰的递增序列+递减序列长度是最大的，但是需要注意同学i既在递增序列中也在递减序列中，相当于递增序列+递减序列把同学i算了两遍，所以最终答案要减一。
所以我们要对每一个同学求他的最长的递增子序列和最长递减的子序列，求最长递减的子序列也就相当于求从右往左的最长递增子序列，根据求最长的递增子序列的通用方法，我们知道dp[i]就表示以i结尾的所有子序列中，最长的上升子序列。本题我们要开两个dp数组，分别维护从左往右的最长递增子序列和从右往左的最长递增子序列。

代码

#include<iostream>#include<algorithm>usingnamespace std;constint N =110;//dp1维护从左往右的最长上升子序列//dp2维护从左往右的最长上升子序列int a[N], dp1[N], dp2[N];int n;intmain(){ cin >> n;for(int i =1; i <= n; i++){ cin >> a[i];}//初始化//按序填表//1.填dp1数组for(int i =1; i <= n; i++){ dp1[i]=1;for(int j =1; j < i; j++){if(a[j]< a[i]) dp1[i]=max(dp1[i], dp1[j]+1);}}//2.填dp2数组for(int i = n; i >=1; i--){ dp2[i]=1;for(int j = n; j > i; j--){if(a[j]< a[i]) dp2[i]=max(dp2[i], dp2[j]+1);}}//输出结果int ret =0;for(int i =1; i <= n; i++){//因为中间i的同学算了两遍，所以需要减一 ret =max(ret, dp1[i]+ dp2[i]-1);} cout << n - ret;return0;}

牛可乐和最长公共子序列

题目描述

题目解析
痛点：存储字符串问题！用string存储下标从0开始！
解决方案：
1、修改下标映射：i -> i - 1 j->j - 1
2、s = " " + s; + s;

本题小编不仅会讲题解，还会介绍一下如何分析两个数组的dp问题。
1、初始化
用一个二维数组dp[i][j]，表示s字符串1到i区间内和t字符串1到j区间内，所有子序列中，最长公共子序列的长度。
2、状态转移方程
状态转移方程要分两种情况讨论：
1、当遍历到两个字符串相同的元素时（s[i] == t[j]），表示这个相同的元素的最长公共子序列的元素之一，要把这个这一对相同的元素选上，也就是把当前公共子序列长度在之前的基础上加1，那要如何找到之前的公共子序列长度呢？其实之前的公共子序列长度就是s字符串1到i - 1区间内和t字符串1到j区间内的最长公共子序列的长度，也就是dp[i - 1][j - 1]，所以这种情况的状态转移方程：
dp[i][j] = dp[i - 1][j - 1] + 1
2、当遍历到两个字符串不同的元素时（s[i] != t[j]），一定不会把这一对不同的元素选到，这时为了填dp[i][j]就需要退而求其次，求在不看s[i]的情况下的最长公共子序列、在不看t[j]的情况下的最长公共子序列和求在不看s[i]并且不看t[j]的情况下的最长公共子序列，也就是分三种情况讨论：
在s数组的1到i区间和t数组的1到j - 1区间找最长公共子序列
在s数组的1到i - 1区间和t数组的1到j区间找最长公共子序列
在s数组的1到i - 1区间和t数组的1到j-1区间找最长公共子序列
dp[i][j]就是在这三种情况中取最值，但对于这种三种情况中取最值的逻辑，因为情况3是包含在情况1、2中的，所以情况3的方案一定小于等于情况1、2，所以在前两种情况中取最值即可。
dp[i][j] = max（dp[i][j - 1]，dp[i - 1][j]）

3、初始化
全部为0即可，因为本题的长度必定大于0，0不会干扰max取最大值的逻辑。
本题虽然是多组测试用例，但是填表是覆盖并且有顺序的，所以每组用例不用重置。
4、填表顺序
根据状态转移方程，填[i][j]时会用到左、上、和左上三个位置的格子，所以填表顺序是从上往下、从左往右。

5、输出结果
假设s字符串长度为n，t字符串长度为m:
dp[n][m]

代码

#include<iostream>#include<string>#include<algorithm>usingnamespace std;constint N =5010;int dp[N][N]; string s, t;intmain(){while(cin >> s >> t){int n = s.size();int m = t.size();//初始化//按序填表for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){if(s[i -1]== t[j -1]){ dp[i][j]= dp[i -1][j -1]+1;}else{ dp[i][j]=max(dp[i -1][j], dp[i][j -1]);}}}//输出结果 cout << dp[n][m]<< endl;}return0;}

编辑距离

题目描述

题目解析
1、状态表示
本题思路继续延续上一题的双数组dp问题，状态表示也类似：dp[i][j]表示把s字符串的1到i子字符串变成t字符串的1到j子字符串的最少操作次数。
2、状态转移方程
还是和上一题类似分两种情况讨论：
1、当遍历到两个字符串相同的元素时（s[i] == t[j]），说明此时不需要修改s数组最后一个元素，也就是对于dp[i][j]来说不需要将操作数加一，仅需要拿到把s字符串的1到i - 1子字符串变成t字符串的1到j - 1子字符串的最少操作次数即可，拿到的该最少操作次数为dp[i][j]的取值。
2、当遍历到两个字符串不同的元素时（s[i] != t[j]），说明此时需要修改s数组最后一个元素，因为题目给出了三种修改方式，所以这里我们要分三种情况讨论：
1.删除s字符串最后一个元素，然后把s字符串的1到i - 1子字符串变为t字符串，把s字符串的1到i - 1子字符串变为t字符串的最少操作次数在dp[i - 1][j]中，因为有删除操作，所以还需要加1。dp[i][j] = dp[i - 1][j] + 1

2、在s字符串最后面插入t字符串的最后一个元素，然后把s字符串的1到i字符串变为t字符串的1到j - 1子t子字符串。dp[i][j] = dp[i][j - 1] + 1

3、把s字符串最后一个元素改为t字符串最后一个元素，然后把s字符串的1到i - 1子字符串变为t字符串的1到j - 1子字符串。dp[i][j] = dp[i - 1][j - 1] + 1

3、初始化
本题初始化需要结合题目的实际意义，虽然题目数据范围的字符串长度从1开始，但是对于本题来说，研究字符串为空时还是有必要的，当把一个空串转换为一个长度为1的字符串时最少字符操作次数是1（插入1次），同理把一个空串转换为一个长度为2的字符串时最少字符操作次数是2，所以对于dp数组的边界情况dp[0][1]要初始化为1，dp[0][2]要初始化为2，依次类推。
当把长度为1的字符串转换为一个空串时最少字符操作次数是1（删除一次），同理当把长度为2的字符串转换为一个空串时最少字符操作次数是2，所以对于dp数组的边界情况dp[1][0]要初始化为1，dp[2][0]要初始化为2，依次类推。

4、填表顺序
从上往下，从左往后
5、输出结果
dp[n][m]

代码

#include<iostream>#include<string>#include<algorithm>usingnamespace std;constint N =2010;int dp[N][N]; string s, t;intmain(){ cin >> s >> t;int n = s.size();int m = t.size();//初始化for(int i =1; i <= n; i++){ dp[i][0]= i;}for(int i =1; i <= m; i++){ dp[0][i]= i;}//按序填表for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){if(s[i -1]== t[j -1]){ dp[i][j]= dp[i -1][j -1];}else{//删int a = dp[i -1][j]+1;//插int b = dp[i][j -1]+1;//改int c = dp[i -1][j -1]+1; dp[i][j]=min({ a, b, c });}}}//输出结果 cout << dp[n][m]<< endl;return0;}

以上就是小编分享的全部内容了，如果觉得不错还请留下免费的赞和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~