动态规划--线性DP

动态规划--线性DP

Lionlnuc
Lionlnuc Lv4
  2026-02-23 2026-02-23 创建   2026-02-23 2026-02-23 更新      

线性 dp–数字三角形模型

数字三角形 Number Triangles

题目链接：
P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles - 洛谷
思路：
把这个三角抽象为二维数组。
动态规划，我们设 表示从 到 的所有方案的集合的最大值。这个点可以由 或者 走过来。
所以状态转移方程为 。
答案就是最下面一层的最大值。
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=1050;
int a[N][N];
int dp[N][N];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
        }
    }
    int ans=-1e18;
    for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);
    cout<<ans<<endl;
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

U280643 摘花生

题目链接：
U280643 摘花生 - 洛谷
思路：
数字三角形模型，我们可以开一个二维数组 dp[i][j] 来表示从 走到 的所有路线所能采摘到花生数量的最大值，最后答案为 。
推导状态转移方程，由于题目限制， 点只能从 或 到达，所以最终方程为 。
还可以进行优化，由于第 i 层只依赖于第 i 层和第 i-1 层，所以可以优化为一维数组。在当前层可以由上一层的该列到达或者由当前层的前列到达。
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=150;
int w[N][N];
int dp[N][N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
        }
    }
    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])+w[i][j];
        }
    }
    cout<<dp[n][m]<<endl;
}
/*一维数组优化空间
//用dp[m]来表示当前计算行第m列的最大值，当计算结束后直接输出dp[m]即可
//记得及时清理数组
void solve()
{
    int n,m;
    cin>>n>>m;
    int w;
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w;
            dp[j]=max(dp[j-1],dp[j])+w;
        }
    }
    cout<<dp[m]<<endl;
}
*/
signed main(){
	IOS
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

最低通行费

题目链接：
T118735 [ybt1287]最低通行费 - 洛谷
思路：
题目限制了不能超过 这其实就是不能往回走。所以我们的状态表示 仍然是从 走到 的所有方案的集合的最小值。
点只能从 或 到达，所以最终方程为 。
求最小值，那么初始化为最大值。
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=1050;
int w[N][N];
int dp[N][N];
void solve()
{
    int n;
    cin>>n;
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==1&&j==1)dp[1][1]=w[1][1];
            else dp[i][j]=min(dp[i-1][j],dp[i][j-1])+w[i][j];
        }
    }
    cout<<dp[n][n];
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

方格取数

题目链接：
P1004 [NOIP 2000 提高组] 方格取数 - 洛谷
思路：
如果只走一次使用 来表示从 走到 （） 所有路径集合的最大值。状态转移公式为 。
不同的是这个题目要求走两次，那么以 来表示分别走到 、 的路径最大值。四维不太好做，可以发现只有当 时才可能踩到重复的格子。
这样我们就可以用三维数组 来表示分别走到 、 的路径最大值。
267492f6f782674a89ff693eb5afb247.jpg|655x415
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=15;
int w[N][N];
int dp[2*N][N][N];
void solve()
{
    int n;
    cin>>n;
    int a,b,c;
    while(cin>>a>>b>>c){
        w[a][b]=c;
    }
    for(int k=2;k<=n*2;k++){
        for(int i1=1;i1<=n;i1++)
        {
            for(int i2=1;i2<=n;i2++)
            {
                int j1=k-i1,j2=k-i2;
                if(j1>0&&j2>0&&j1<=n&&j2<=n){
                    int m=w[i1][j1];
                    if(i1!=i2)m+=w[i2][j2];
                    int &x=dp[k][i1][i2];
                    x=max(x,dp[k-1][i1-1][i2-1]+m);
                    x=max(x,dp[k-1][i1-1][i2]+m);
                    x=max(x,dp[k-1][i1][i2-1]+m);
                    x=max(x,dp[k-1][i1][i2]+m);
                }
            }
        }
    }
    cout<<dp[2*n][n][n];
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

传纸条

题目链接：
P1006 [NOIP 2008 提高组] 传纸条 - 洛谷
思路：
这个题目同上面方格取数的思路，这里的好感度可以看作是格子里的数字，每个数字只能用一次。
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=55;
int w[N][N];
int dp[2*N][N][N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
        }
    }
    for(int k=2;k<=n+m;k++){
        for(int i1=1;i1<=n;i1++)
        {
            for(int i2=1;i2<=n;i2++)
            {
                int j1=k-i1,j2=k-i2;
                if(j1>0&&j2>0&&j1<=m&&j2<=m){
                    int t=w[i1][j1];
                    if(i1!=i2)t+=w[i2][j2];
                    int &x=dp[k][i1][i2];
                    x=max(x,dp[k-1][i1-1][i2-1]+t);
                    x=max(x,dp[k-1][i1-1][i2]+t);
                    x=max(x,dp[k-1][i1][i2-1]+t);
                    x=max(x,dp[k-1][i1][i2]+t);
                }
            }
        }
    }
    cout<<dp[m+n][n][n];
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

线性 dp–最长上升子序列模型

最长上升子序列

题目链接：
B3637 最长上升子序列 - 洛谷
思路：
用 f[i] 表示所有以 a[i] 结尾的严格单调上升子序列长度，初始时 f[i]=1 ，枚举序列的倒数第二个数，用 j(0<j<i) 来表示，若 a[j]<a[i] 则 f[i]=max(f[i],f[j]+1)。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N=5500;
int a[N];
int f[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j])
            f[i]=max(f[i],f[j]+1);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
    cout<<ans;
}

使用二分查找可以减少时间复杂度，对于新进来的元素 a[i]，如果 a[i] 大于 f[cnt]，则 f 数组长度加一，将 a[i] 添加进去。反之用 a[i] 替换掉 f 数组中第一个大于或者等于 a[i] 的元素。这样虽然 f 数组中存的不是最长上升子序列，但是长度是相等的。

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
26
27
28
29
30
31
32
33
const int N=1e5+5;
int a[N];
int f[N];
int cnt;
int find(int x){
    int l=1,r=cnt;
    while(l<r){
        int mid=(l+r)>>1;
        if(f[mid]>=x){
            r=mid;
        }else l=mid+1;
    }
    return l;
}
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    f[++cnt]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(f[cnt]<a[i])f[++cnt]=a[i];
        else{
            int idx=find(a[i]);
            f[idx]=a[i];
        }
    }
    cout<<cnt;
}

怪盗基德的滑翔翼

题目链接：
U234151 怪盗基德的滑翔翼 - 洛谷
思路：
这个题其实就是求一个最长下降子序列，可以选任意楼为起点，假如选择 a[i] 为起点，那么最长距离为以 a[i] 为结尾的最长上升子序列。所以可以正向做一次反向再求一次得到答案最大值。
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int N=1e5+5;
int a[N];
int f[N];
int b[N];
void solve()
{
    int n;
    cin>>n;
    memset(b,0,sizeof b);
    memset(f,0,sizeof f);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=1;
        b[i]=1;//这里用了两个数组可能不好看
    }
    for(int i=n;i>0;i--)
    {
        for(int j=n;j>i;j--){
            if(a[j]<a[i])
            f[i]=max(f[i],f[j]+1);
        }
    }
    int ans=0;
    // for(int i=1;i<=n;i++)
    // {
    //     ans=max(ans,f[i]);
    // }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])b[i]=max(b[i],b[j]+1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,max(f[i],b[i]));
    }
    cout<<ans<<endl;
}

登山

题目链接：
U247946 登山 - 洛谷
思路：
这里的要求一旦开始下降就不能再上升，相邻两个景点的海拔不能相同。按照编号递增顺序来浏览，那么就是先单调上升再单调下降。这样我们就要在中间选一个点，分别向两边走，取最大值。这样的话就先从左向右做一遍最长上升子序列再从右向左做一遍最长上升子序列，再进行枚举答案取最大值即可。
代码：

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
26
27
28
29
30
31
32
33
const int N=1e5+5;
int a[N];
int f[N],b[N];
void solve()
{
    int n;
    cin>>n;
    memset(f,0,sizeof f);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])f[i]=max(f[i],f[j]+1);
        }
    }
    for(int i=n;i>0;i--){
        b[i]=1;
        for(int j=n;j>i;j--){
            if(a[j]<a[i])b[i]=max(b[i],b[j]+1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,f[i]+b[i]-1);
    }
    cout<<ans<<endl;
}

合唱队形

题目链接：
P1091 [NOIP 2004 提高组] 合唱队形 - 洛谷
思路：
这个题目要求最少的出队人数，那么其实和上一题是相似的，我们找到满足这个类型队伍的最大值，用 n 减去即可。
代码：
代码只需要将输出修改为 cout<<n-ans<<endl。

友好城市

题目链接：
P2782 友好城市 - 洛谷
思路：
先把一边排序，另一边的最长上升子序列的长度就是最多的的数量，一边已经确定好顺序了，只要保证另一边也是升序，就一定不会交叉。只用 dp 会超时，用二分优化。
同样的用一个数组 f 来存，如果 a[i] 大于 f 最后一个数那么就可以放进去，长度加一。反之则找 f 数组中第一个大于 a[i] 的数替换。
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
#define x first
#define y second
const int N=2e5+5;
PII a[N];
int f[N],b[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x;
        cin>>a[i].y;
    }
    sort(a+1,a+1+n);
    int cnt=0;
    f[++cnt]=a[1].y;
    for(int i=2;i<=n;i++)
    {
        if(a[i].y>f[cnt])f[++cnt]=a[i].y;
        else{
            int idx=upper_bound(f+1,f+cnt+1,a[i].y)-f;
            f[idx]=a[i].y;
        }
        
    }
    cout<<cnt;
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

最大上升子序列和

题目链接：
T285024 最大上升子序列和 - 洛谷
思路：
这个题目使用 f[i] 表示所有以 a[i] 结尾的上升子序列和的最大值。
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
#define x first
#define y second
const int N=2e5+5;
int a[N];
void solve()
{
    int n;
    cin>>n;
    vector<int> f(n+5);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])f[i]=max(f[i],f[j]+a[i]);
        }
    }
    int ans=*max_element(f.begin(),f.end());
    cout<<ans;
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

导弹拦截

题目链接：
P1020 [NOIP 1999 提高组] 导弹拦截 - 洛谷
思路：
第一问求最长不上升子序列。
第二问考虑贪心：对于每个数，如果现有的子序列的结尾都小于当前数字，那么开一个新的子序列。否则将它放到结尾大于等于它的最小子序列的后面。
不会证明 🥱
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
#define x first
#define y second
const int N=2e5+5;
int q[N];
int a[N];
int f[N];
int cnt=0;
void solve()
{
    int n=0,x;
    while(cin>>x){
        a[++n]=x;
    }
    f[++cnt]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(f[cnt]>=a[i])f[++cnt]=a[i];
        else{
            int idx=upper_bound(f+1,f+1+cnt,a[i],greater<int>())-f;
            f[idx]=a[i];
        }
    }
    cout<<cnt<<endl;
    memset(q,0x3f,sizeof q);
    cnt=1;
    for(int i=1;i<=n;i++)
    {
        if(q[cnt]>=a[i]){
            int idx=lower_bound(q+1,q+1+cnt,a[i])-q;
            q[idx]=a[i];
        }else{
            q[++cnt]=a[i];
        }
    }
    cout<<cnt;
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

最长公共子序列

题目链接：
897. 最长公共子序列 - AcWing题库
思路：
用 f[i][j] 表示 a 的前 i 个字母，和 b 的前 j 个字母的最长公共子序列长度。
以 a[i] 、b[j] 是否在子序列中划分为四类：

  1. a[i] 不在，b[j] 不在 此时 max = f[i-1][j-1]。
  2. a[i] 在，b[j] 不在 此时 max=f[i−1][j]。
  3. a[i] 不在，b[j] 在 此时 max=f[i][j-1]。
  4. a[i] 在，b[j] 在 此时 max = f[i-1][j-1]+1 。
    1）情况是包含在 2）3）中的。
    代码：
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
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define endl '\n'
const int N=1010;
char a[N],b[N];
int n,m;
int f[N][N];
void solve(){
    cin>>n>>m;
    cin>>a+1>>b+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]);
            if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m];
}
signed main(){
    IOS
    int t=1;
    while(t--){
        solve();
    }
}

两个排列的最长公共子序列

题目链接：
P1439 两个排列的最长公共子序列 - 洛谷
思路：
这个题目用上面的方法会超时。我们可以把第一个序列中第 i 个数映射为 i，在第二个序列中也进行修改。比如原序列为 A={1,2,5,4,3} B={5,3,4,2,1} 映射后为 A={1,2,3,4,5} B={3,5,4,2,1} 这样将求最长公共子序列问题转为求 B 序列的最长上升子序列。这样就可以用二分优化。
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define endl '\n'
const int N=1e5+5;
int a[N],b[N];
int n;
int f[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a[x]=i;//这样使用A数组存储映射关系，方便B数组查询。
    }
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        b[i]=a[x];
    }
    int cnt=0;
    f[++cnt]=b[1];
    for(int i=2;i<=n;i++){
        if(b[i]>f[cnt])f[++cnt]=b[i];
        else{
            int idx=lower_bound(f+1,f+1+cnt,b[i])-f;
            f[idx]=b[i];
        }
    }
    cout<<cnt;
}
signed main(){
    IOS
    int t=1;
    while(t--){
        solve();
    }
}

Missile Defence System

题目链接：
P10490 Missile Defence System - 洛谷
思路：
一个导弹有四种选择：
1）用一个已经建立好的递增拦截装置拦截；
2）用一个已经建立好的递减拦截装置拦截；
3）新建一个递增拦截装置；
4）新建一个递减拦截装置。
考虑深搜 DFS，我们要进行搜索这颗导弹属于上升子序列还是下降子序列，搜索这颗导弹属于哪一个上升/下降子序列。
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define PII pair<int,int>
#define x first
#define y second
const int N=55;
int up[N],down[N];
int a[N];
int ans;
int n;
//前u个导弹\上升系统个数su\和下降系统个数sd
void dfs(int idx,int su,int sd){
    if(su+sd>=ans)return;
    //最优性剪枝：当目前答案已经大于已知最优答案时，直接回溯
    if(idx==n){
        ans=su+sd;
        return;
    }
    /*
    使用上升系统拦截。
    如果当前已有的上升拦截系统的高度都大于第u个导弹高度，则重新开一套系统
    否则，就找到当前低于第u个导弹最高拦截系统来负责拦截
    */
    int k=0;
    while(k<su&&up[k]>=a[idx])k++;
    int t=up[k];
    up[k]=a[idx];
    if(k>=su)dfs(idx+1,su+1,sd);
    else dfs(idx+1,su,sd);
    up[k]=t;//恢复现场
    /*
    用下降拦截系统来拦截
    如果当前已有的下降拦截系统的高度都小于第u个导弹高度，则重新开一套系统
    否则，则由当前大于第u个导弹最低拦截系统来负责拦截
    */
    k=0;
    while(k<sd&&down[k]<=a[idx])k++;
    t=down[k];
    down[k]=a[idx];
    if(k>=sd)dfs(idx+1,su,sd+1);
    else dfs(idx+1,su,sd);
    down[k]=t;
}
void solve()
{
    while(cin>>n){
        if(n==0)break;
        for(int i=0;i<n;i++)cin>>a[i];
        ans=n;
        dfs(0,0,0);
        cout<<ans<<endl;
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

LCIS

题目链接：
P10954 LCIS - 洛谷
思路：
设 f[i][j] 表示 a 的前 i 个数和 b 的前 j 个数并以 b[j] 结尾的最大长度。
当 a[i]=b[j] 时，只需要在前面找到一个可以把 b[j] 接上去的最长公共上升子序列，答案为 max(f[i-1][k])+1。
当 a[i]≠b[j] 时，f[i][j]=f[i-1][j]
代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*三重循环做法*/
const int N=3100;
int a[N],b[N];
int n;
int f[N][N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(a[i]==b[j]){
                int mx=0;
                for(int k=1;k<j;k++){
                    if(b[k]<b[j])
                        mx=max(mx,f[i-1][k]);
                }
                f[i][j]=mx+1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,f[n][i]);
    }
    cout<<ans;
}
/*
	可以发现每次循环所得到的mx值满足a[i]>b[k]的f[i-1][k]+1的前缀最大值，所以我们直接将这步提出来。
*/
const int N=3100;
int a[N],b[N];
int n;
int f[N][N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)
    {
        int mx=0;
        for(int j=1;j<=n;j++)
        {
            if(a[i]!=b[j])f[i][j]=f[i-1][j];
            if(a[i]==b[j])f[i][j]=max(mx,f[i][j])+1;
            if(a[i]>b[j])mx=max(mx,f[i-1][j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,f[n][i]);
    }
    cout<<ans;
}
  • 标题: 动态规划--线性DP
  • 作者: Lionlnuc
  • 创建于 : 2026-02-23 00:00:00
  • 更新于 : 2026-02-23 00:00:00
  • 链接: https://lionlnuc.github.io/2026/02/23/动态规划01/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
动态规划--线性DP
  1. 线性 dp–数字三角形模型
    1. 数字三角形 Number Triangles
    2. U280643 摘花生
    3. 最低通行费
    4. 方格取数
    5. 传纸条
  2. 线性 dp–最长上升子序列模型
    1. 最长上升子序列
    2. 怪盗基德的滑翔翼
    3. 登山
    4. 合唱队形
    5. 友好城市
    6. 最大上升子序列和
    7. 导弹拦截
    8. 最长公共子序列
    9. 两个排列的最长公共子序列
    10. Missile Defence System
    11. LCIS