1
int maxSubArray(vector<int>& nums) {
2
    int pre=nums[0],ans=nums[0];
3
  for(int i=1;i<nums.size();i++){
4
    if(pre>=0) pre+=nums[i];
5
    else pre=nums[i];
6
    ans=max(pre,ans);
7
  }
8
  return ans;
9
}

要更进一步的弄懂这个问题，可以顺便把最大子数组的范围求出来

1
int left=0,right=0;
2
int maxSubArray(vector<int>& nums) {
3
    int pre=nums[0],ans=nums[0],l=0,r=0;
4
  for(int i=1;i<nums.size();i++){
5
    if(pre>=0){
6
      pre+=nums[i];
7
      r++;
8
    }
9
    else{
10
      pre=nums[i];
11
      r++;
12
      l=r;
13
    }
14
    if(pre>ans){
15
      ans=pre;
16
      left=l;
17
      right=r;
18
    }
19
  }
20
  return ans;
21
}

198. 打家劫舍 #

1
int rob(vector<int>& nums) {
2
  int n=nums.size();
3
  if(n==1) return nums[0];
4
  if(n==2) return max(nums[0],nums[1]);
5
  int pre=max(nums[0],nums[1]),ppre=nums[0];
6
  for(int i=2,cur;i<n;i++){
7
    cur=max({nums[i],pre,ppre+nums[i]});
8
    ppre=pre;
9
    pre=cur;
10
  }
11
  return pre;
12
}

P1216 数字三角形 Number Triangles - 洛谷 #

B3637 最长上升子序列 - 洛谷 #

最基础的LIS问题

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
const int N = 51;
6
const int MAXN = 1e9;
7

8
const ll MOD = 998244353;
9
const ll INF = 4e18;
10

11
void solve(){
12
  int n;
13
  cin>>n;
14
  vector<int> arr(n);
15
  vector<int> dp(n,0);
16
  for(int i=0;i<n;i++){
17
    cin>>arr[i];
18
  }
19
  int ans=0;
20
  for(int i=0;i<n;i++){
21
    dp[i]=1;
22
    for(int j=0;j<i;j++){
23
      if(arr[j]<arr[i]){
24
        dp[i]=max(dp[i],dp[j]+1);
25
      }
26
    }
27
    ans=max(ans,dp[i]);
28
  }
29
  // for(int i=0;i<n;i++){
30
  //   ans=max(ans,dp[i]);
31
  // }
32
  cout<<ans;
33
}
34

35
int main(){
36
  ios::sync_with_stdio(0);
37
  cin.tie(0),cout.tie(0);
38
  int T=1;
39
  // cin>>T;
40
    while(T--){
41
      solve();
42
    }
43
    // while(scanf("%d,%d",&n,&k)!=EOF){
44
      // solve(n,k);
45
    // }
46
  return 0;
47
}

上述复杂度为o( $n^2$ ),可以用二分查找优化内层循环使得复杂度变为o( $nlogn$ ),如果要求不下降子序列问题 $b.back()<=a[i]$ 即可

1
ll n;
2

3
void solve() {
4
  cin>>n;
5
  vector<int> a(n),b;
6
  for(int i=0;i<n;i++){
7
    cin>>a[i];
8
  }
9
  for(int i=0;i<n;i++){
10
    if(b.empty()||b.back()<a[i]){
11
      b.push_back(a[i]);
12
    }
13
    else{
14
      auto it=lower_bound(b.begin(),b.end(),a[i]);
15
      *it=a[i];
16
    }
17
  }
18
  cout<<b.size();
19
}

最长公共子序列 LCS#

求两个字符串的最长公共子序列长度。

输入格式:#

输入长度≤100的两个字符串。

输出格式:#

输出两个字符串的最长公共子序列长度。

输入样例1:#

1
ABCBDAB
2
BDCABA

输出样例1:#

1
4

输入样例2:#

1
ABACDEF
2
PGHIK

输出样例2:#

1
0

解法#

1
string a,b;
2

3
void solve() {
4
  cin>>a>>b;
5
  int n=a.size(),m=b.size();
6
  vector<vector<int>> dp(n+1,vector<int>(m+1,0));
7
  vector<vector<int>> pre(n+1,vector<int>(m+1,0));
8
  for(int i=1;i<=n;i++){
9
    for(int j=1;j<=m;j++){
10
      if(a[i-1]==b[j-1]){
11
        dp[i][j]=dp[i-1][j-1]+1;
12
      }
13
      else
14
      dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
15
    }
16
  }
17
  cout<<dp[n][m];
18
}

单序列模型#

P1091 [NOIP 2004 提高组] 合唱队形 - 洛谷 #

优化#

P1020 [NOIP 1999 提高组] 导弹拦截 - 洛谷 #

需要用到二分维护最长不上升子序列来优化，第二小问用到Dilworth定理通过求最长上升子序列来得到最少需要几台机器拦截导弹，用到greater比较器使得lower_bound在递减序列中使用

P2008 大朋友的数字 - 洛谷 #

1
int n;
2

3
void solve() {
4
  cin>>n;
5
  vector<ll> a(n),dp(n,0),res(n,0);
6
  for(int i=0;i<n;i++){
7
    cin>>a[i];
8
  }
9
  for(int i=0;i<n;i++){
10
    dp[i]=1;
11
    for(int j=0;j<i;j++){
12
      if(a[j]<=a[i]&&dp[j]>=dp[i]){
13
        dp[i]=max(dp[i],dp[j]+1);
14
        res[i]=res[j];
15
      }
16
    }
17
    res[i]+=a[i];
18
  }
19
  for(int i=0;i<n;i++){
20
    cout<<res[i]<<" ";
21
  }
22
}

P8776 [蓝桥杯 2022 省 A] 最长不下降子序列 - 洛谷 #

1
ll n,k;
2
void solve(){
3
  cin>>n>>k;
4
  vector<int> arr(n);
5
  for(int i=0;i<n;i++){
6
    cin>>arr[i];
7
  }
8
  vector<int> dp,right(n),b=arr;
9
  reverse(b.begin(),b.end());
10
  for(int i=0;i<n;i++){
11
    if(dp.empty()||b[i]<=dp.back()){
12
      dp.push_back(b[i]);
13
      right[i]=dp.size();
14
    }
15
    else{
16
      auto it=upper_bound(dp.begin(),dp.end(),b[i],greater<int>());
17
      *it=b[i];
18
      right[i]=(it-dp.begin())+1;
19
    }
20
  }
21
  reverse(right.begin(),right.end());
22
  dp.clear();
23
  ll ans=0,pre=0;
24
  for(int i=k;i<n;i++){
25
    if(!dp.empty()){
26
      pre=lower_bound(dp.begin(),dp.end(),arr[i])-dp.begin();
27
    }
28
    if(dp.empty()||arr[i-k]>=dp.back()){
29
      dp.push_back(arr[i-k]);
30
    }
31
    else{
32
      auto it=upper_bound(dp.begin(),dp.end(),arr[i-k]);
33
      *it=arr[i-k];
34
    }
35
    ans=max(ans,pre+k+right[i]);
36
  }
37
  ans=max(ans,ll(dp.size())+k);
38
  cout<<ans<<"\n";
39
}

环状序列模型#

918. 环形子数组的最大和 #

P2642 最大双子段和 - 洛谷逻辑上数组首尾相连，实际上，答案有两种情况，一种是连续不断的子数组，另一种是中间有一段中断的“两个子数组”，后者就是整个数组和-最小子数组的情况，跑两次比较大小即可当然，后者的这个算法有一个问题，就是如果整个数组都为正数或者都为负数，那么最大子数组=最小子数组=数组之和，那么这个算法算出来等于0，如果是都为负数的情况，题目要求子数组>=1那么就会出问题，需要特判

1
int maxSubarraySumCircular(vector<int>& nums) {
2
    int pre=nums[0],res=nums[0],ans=nums[0],n=nums.size(),sum=nums[0];
3
  for(int i=1;i<n;i++){
4
    sum+=nums[i];
5
    if(pre>0){
6
      pre+=nums[i];
7
    }
8
    else{
9
      pre=nums[i];
10
    }
11
    ans=max(ans,pre);
12
  }
13
  pre=nums[0];
14
  for(int i=1;i<n;i++){
15
    if(pre<0){
16
      pre+=nums[i];
17
    }
18
    else{
19
      pre=nums[i];
20
    }
21
    res=min(res,pre);
22
  }
23
  if(res==sum){
24
    return ans;
25
  }
26
  else{
27
    return max(ans,sum-res);
28
  }
29
}

P1121 环状最大两段子段和 - 洛谷 #

转换为区间的暴力解

1
int n;
2
void solve(){
3
  cin>>n;
4
  vector<int> a(2*n);
5
  for(int i=0;i<n;i++){
6
    cin>>a[i];
7
    a[n+i]=a[i];
8
  }
9
  vector<vector<ll>> dp(2*n,vector<ll>(2*n,-MAXN));
10
  for(int l=0,r=n;r<=2*n;l++,r++){
11
    for(int i=l;i<r;i++){
12
      if(i==l) dp[l][i]=a[l];
13
      else{
14
        if(dp[l][i-1]>0){
15
          dp[l][i]=a[i]+dp[l][i-1];
16
        }
17
        else{
18
          dp[l][i]=a[i];
19
        }
20
      }
21
    }
22
  }
23
  ll ans=-MAXN;
24
  for(int l=0;l<n;l++){
25
    for(int k=l;k<l+n-1;k++){
26
      for(int r=k+1;r<=n+l-1&&r<2*n;r++){
27
        ans=max(ans,dp[l][k]+dp[k+2][r]);
28
      }
29
    }
30
  }
31
  cout<<ans;
32
}

可以转换为求一段一段序列中两段最大和的和与一段序列中总和减去两端最小的差作比较：

000 A 000 B 000 → 直接找两个 A/B 最大 A 000 B 000 A → 总和减掉两个 000 最小

答案如下：

1
int n;
2
void solve(){
3
  cin>>n;
4
  vector<int> a(n);
5
  ll sum=0;
6
  for(int i=0;i<n;i++){
7
    cin>>a[i];
8
    sum+=a[i];
9
  }
10
  vector<ll> dp(n,0),lb(n,0),rb(n,0);
11
  dp[0]=lb[0]=a[0];
12
  for(int i=1;i<n;i++){
13
    if(dp[i-1]>0){
14
      dp[i]=a[i]+dp[i-1];
15
    }
16
    else dp[i]=a[i];
17
    lb[i]=max(lb[i-1],dp[i]);
18
  }
19
  dp[n-1]=rb[n-1]=a[n-1];
20
  for(int i=n-2;i>=0;i--){
21
    if(dp[i+1]>0){
22
      dp[i]=a[i]+dp[i+1];
23
    }
24
    else dp[i]=a[i];
25
    rb[i]=max(dp[i],rb[i+1]);
26
  }
27
  ll ans1=-MAXN,ans2=MAXN;
28
  for(int i=0;i<n-1;i++){
29
    ans1=max(ans1,lb[i]+rb[i+1]);
30
  }
31
  dp[0]=lb[0]=a[0];
32
  for(int i=1;i<n;i++){
33
    if(dp[i-1]<0){
34
      dp[i]=a[i]+dp[i-1];
35
    }
36
    else dp[i]=a[i];
37
    lb[i]=min(lb[i-1],dp[i]);
38
  }
39
  if(lb[n-1]==sum){
40
    cout<<ans1;
41
    return;
42
  }
43
  dp[n-1]=rb[n-1]=a[n-1];
44
  for(int i=n-2;i>=0;i--){
45
    if(dp[i+1]<0){
46
      dp[i]=dp[i+1]+a[i];
47
    }
48
    else dp[i]=a[i];
49
    rb[i]=min(dp[i],rb[i+1]);
50
  }
51
  for(int i=0;i<n-1;i++){
52
    ans2=min(ans2,lb[i]+rb[i]);
53
  }
54
  cout<<max(ans1,sum-ans2);
55
}

进阶dp的优化#

P9242 [蓝桥杯 2023 省 B] 接龙数列 - 洛谷 #

仔细分析和求最长上升子序列差不多，LIS的做法是判断dp[i]的尾和dp[j]的头是否相等，如果相等，使用LIS的状态转移方程持续更新dp，但是数据量更大，o( $n^2$ )会tle，所以需要一定的优化，这里换一种遍历和dp的存储方式（同时也更改了状态转移方程）为什么会超时，就是因为dp存了大量的数据，然后更新dp的时候计算量大，导致超时，这种题注意到以i为尾的更新方式只有10中，如果我的dp表也只记录十种，那么不就大大减少计算量了吗

1
int n;
2
int ans=0;
3

4
void solve() {
5
  cin>>n;
6
    vector<string> a(n);
7
    for(int i=0;i<n;i++){
8
        cin>>a[i];
9
    }
10
    vector<int> dp(10,0);
11
    for(int i=0;i<n;i++){
12
        int f=a[i][0]-'0',t=a[i][a[i].size()-1]-'0';
13
        dp[t]=max(dp[t],dp[f]+1);
14
    }
15
    for(int i=0;i<10;i++){
16
        ans=max(ans,dp[i]);
17
    }
18
    cout<<n-ans; // 最后，要求的是最少修改量，因此总数减掉最长的情况即可
19
}

如果这篇文章对你有帮助，欢迎分享给更多人！

动态规划-线性dp

https://blog.hydrodyio.xyz/posts/动态规划-线性dp/

作者

Hydroiody

发布于

2026-07-30

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

图论-拓扑排序

动态规划-背包dp

Welcome!

文章更新热度

基础题型#

53. 最大子数组和 #

提一个概念#

题解优化了dp数组#

198. 打家劫舍 #

P1216 数字三角形 Number Triangles - 洛谷 #

B3637 最长上升子序列 - 洛谷 #

U651833 游戏4 - 洛谷 #

最长公共子序列 LCS#

输入格式:#

输出格式:#

输入样例1:#

输出样例1:#

输入样例2:#

输出样例2:#

解法#

单序列模型#

P1091 [NOIP 2004 提高组] 合唱队形 - 洛谷 #

优化#

P1020 [NOIP 1999 提高组] 导弹拦截 - 洛谷 #

354. 俄罗斯套娃信封问题 #

2111. 使数组 K 递增的最少操作次数 #

P2008 大朋友的数字 - 洛谷 #

P8776 [蓝桥杯 2022 省 A] 最长不下降子序列 - 洛谷 #

环状序列模型#

918. 环形子数组的最大和 #

P1121 环状最大两段子段和 - 洛谷 #

进阶dp的优化#

P9242 [蓝桥杯 2023 省 B] 接龙数列 - 洛谷 #

目录

Welcome!

基础题型#

提一个概念#

题解 优化了dp数组#

最长公共子序列 LCS#

输入格式:#

输出格式:#

输入样例1:#

输出样例1:#

输入样例2:#

输出样例2:#

解法#

单序列模型#

优化#

环状序列模型#

进阶dp的优化#

目录

题解优化了dp数组#