【引入】
线性DP，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板
线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值
因此，除了少量问题（如：LIS、LCS、LCIS等）有固定的模板外，大部分都要根据实际问题来推导得出答案
【常见问题】
(一)序列问题
首先，让我们先了解一下子串、子序列还有公共子序列的概念
(1)字符子串：指的是字符串中连续的n个字符，如abcdefg中，ab，cde，fg等都属于它的字串
(2)字符子序列：指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。如abcdefg中，acdg，bdf属于它的子序列，而bac，dbfg则不是，因为它们与字符串的字符顺序不一致
(3)公共子序列：如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。如对序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 来说，序列1,8,7是它们的一个公共子序列
1.LIS问题——最长上升子序列
最长上升子序列（Longest Increasing Subsequence），简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数，对于固定的数组，虽然LIS序列不一定唯一，但LIS的长度是唯一的
状态设计：dp[i]代表以a[i]结尾的LIS的长度
状态转移：dp[i]=max{dp[j]+1，dp[i]} (1<=j< i，a[j]<a[i])
边界处理：dp[i]=1(1<=i<=n)
时间复杂度：O (n^2)
模板：
#include<iostream>
using namespace std;
const int N=105;
int a[N],dp[N];
int main(){
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1; j<i; j++){
if(a[j]<a[i]){
dp[i] = max(dp[i],dp[j]+1);
}
}
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}2. LCS问题——最长公共子序列
最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。对于固定的两个数组，虽然最LCS不一定唯一，但LCS的长度是一定的。查找最长公共子序列与查找最长公共子串的问题不同的地方在于：子序列不需要在原序列中占用连续的位置。最长公共子串（要求连续）和最长公共子序列是不同的
状态设计：dp[i][j]代表以s1[i]，s2[j]结尾的LCS的长度
状态转移：
if(s1[i-1]==s2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}时间复杂度：O(n * m)
模板：
#include<iostream>
using namespace std;
const int N=1005;
int dp[N][N];
int main(){
string s1,s2;
cin>>s1>>s2;
int len1=s1.size(),len2=s2.size();
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(s1[i-1]==s2[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[len1][len2];
return 0;
}3. LCIS问题——最长公共上升子序列
状态设计：dp[i, j]表示s1前i个字符和s2前j个字符且以s2[j]为结尾的LCIS
状态方程：对于当处于(s1[i], s2[j])状态时 ，由于dp状态，s2[j]是一定作为这个状态下LCIS的结尾的，所以对于s1[i]，就有两种情况，将其纳入LCIS或者不纳入，首先先说不讲a[i]纳入LCIS的情况
(1)若是s1[i]!=s2[j]，显然s1[i]与s2[j]是不能进行配对的，那么问题就缩小成了前s1的前i-1个字符与s2的前j个字符且以s2[j]结尾的LCIS，即dp[i-1, j]也就是说，i之前的以s2[j]结尾的序列自然没有改变，仍然是长度仍然是dp[i−1][j]; 若是s1[i]==s2[i] 如果不想要s1[i]与s2[j]进行配对，是不是也会得到上面的结果，故当s1[i]与s2[j]无法配对时，dp[i, j] = dp[i-1, j]
(2)当s1[i]==s2[j]且它们进行配对时，就要在s1串前i-1个字符和s2的前j-1个字符中找到一个最长的序列，设这个序列以t结尾且b[t]<b[j]，是不是就等价于dp[i, j]=max(dp[i-1, t])+1(t >0 &&t<j&&s2[t]<s2[j])
代码：
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=dp[i-1][j];
if(a[i]==b[j]){
for(int k=1;k<j;k++){
if(b[j]>b[k]){
dp[i][j]=max(dp[i][j],dp[i-1][k]+1);
}
}
}
}
}上面代码的时间复杂度为O(n3)，可对其进行O(n2)的优化文章来源：https://www.toymoban.com/news/detail-497803.html
待更新......文章来源地址https://www.toymoban.com/news/detail-497803.html
到了这里，关于[动态规划]——线性DP(LIS/LCS/LCIS等) 详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
