题目解决思路是一行一行的线性思考即称为线性dp。

例题1：数字三角形

链接：898. 数字三角形 - AcWing题库

题面：

 思路：

代码：

#include

using namespace std;

typedef long long ll;

const int N=510,INF=1e9;//定义一个无穷大

int n;

int a[N][N],f[N][N];

//a[i]来存数字三角形当前数字

//f[i][j]用来存到达（i,j）所有路径的最大值

int main(){

    cin>>n;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=i;j++)

            cin>>a[i][j];

  

    for(int i=0;i<=n;i++)

        for(int j=0;j<=i+1;j++)//注意这里要初始化到i+1的范围

            f[i][j]=-INF;

    f[1][1]=a[1][1];//顶点的最大值就是顶点本身

   

    for(int i=2;i<=n;i++)//由于顶点已经赋值了，则从第2行开始

        for(int j=1;j<=i;j++)

            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);//状态转移方程

//要求输出从顶点到底端的路径最大值，这里遍历一遍最底层的数值找到最大值

    int res=-INF;

for(int i=1;i<=n;i++) res=max(res,f[n][i]);

    cout< 
 
例题2：最长递增子序列 
链接：895. 最长上升子序列 - AcWing题库
 
题面：
 
 
 
 
思路：
 
 
 
 
代码：
 
#include

using namespace std;

typedef long long ll;

const int N=1010;

int n,a[N],f[N];

int main(){

    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++){

        f[i]=1;//只含a[i]一个数的情况f[i]表示的长度就是1

        for(int j=1;j 
 
 
拓展：要求输出最长递增的序列，我们只需要开一个新的数组来记录更新的状态就行了
 
 
代码如下：
 
#include

using namespace std;

typedef long long ll;

const int N=1010;

int n;

int a[N],f[N],g[N];

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)

    {

        f[i]=1;

        g[i]=0;//如果g[i]为0，则表示没有更新

        for(int j=1;j 
 
 
例题3：最长公共子序列 
链接：897. 最长公共子序列 - AcWing题库
 
题面：
 
 
 
 
思路：
 
 
 
 
代码：
 
#include

using namespace std;

typedef long long ll;

const int N=1010;

char a[N],b[N];

int n,m,f[N][N];

int main()

{

    cin>>n>>m;

    cin>>a+1>>b+1;//多读一个，后面用到了i-1,j-1(注意范围)

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]);//01,10的情况取最大值

//11的情况要判断a[i]与b[j]是否相同

            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);

        }

    }

    cout<