线性DP从字面上来说，就是在一条线上进行DP。

线性DP不像区间DP有比较固定的模板，所以直接上例题。

最长公共子序列

原题链接

看完题面，可以得到题意就是给你两个序列，然后让你求出这两个序列最长的公共部分有多长。

理解了题面然后就可以进行思考了，既然是线性DP，咱们就应该想，怎么去转移。

首先看题面有两个序列，所以大致可以确定状态量为f[i][j]，因为有两个限制条件。

然后根据闫氏DP分析法可以得到，状态表示有四种，一种是选a[i]，不选b[j]，第二种是不选a[i]，选b[j]，第三种是都不选，最后一种是都选。

那么咱们就可以根据状态表示来写出状态转移方程。

因为f[i-1][j]和[i][j-1]并不能分别代表不选a[i]，选b[j]和选a[i]，不选b[j],但是咱们可以发现，f[i-1][j]是一定全部包含不选a[i]，选b[j]这种情况的，又因为咱们又是求最大值，而不是求和，所以有重复计算是没有关系的。最值问题一定保证的是全面覆盖不需要考虑重复问题。同理f[i][j-1]也是这样。

那么咱们的状态转移方程出来了，思路也出来了。

就可以操着思路写代码了

 #include<bits/stdc++.h>
using namespace std;
char a[1100],b[1100];
int f[1100][1100];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j])
            {
                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            }
        }
    }
    cout<<f[n][m];
}