前言：

今日所学知识点–线性dp
在此进行归纳和总结，以及分享题解

概述：

线性动态规划，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板。

线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。

因此，除了少量问题有固定的模板外，大部分都要根据实际问题来推导得出答案。

实践

题目一：数学三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

解法：自顶向下dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N],w[N][N];
int main()
{
    int n;
    cin >>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>w[i][j];
    dp[1][1]=w[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+w[i][j];
    cout<<max(dp[n][(n+1)/2],dp[n][(n+2)/2]);
    return 0;
}

题目二：最长上升子序列

这是一个简单的动规板子题。
给出一个由n(n<=5000)个不超过1e6的正整数组成的序列。请输出这个序列最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

解法：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace  std;
const int N=1e6;
int q[N];
int dp[N];
int main()
{
    int n,res=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>q[i];
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++)
            if(q[i]>q[j])
                dp[i]=max(dp[j]+1,dp[i]);
    }

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

    return 0;
}

题目三:最长公共子序列

给出两个字符串s1，s2，求出它们最长公共长度子序列的长度

解法：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
const int N=1e3+5;
char a[N],b[N];
int dp[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    cin>>a+1>>b+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
        }
    cout<<endl;
    cout<<dp[n][m];
    return 0;
}