一、动态规划的本质——以01背包为例

动态规划（DP）的核心思想是：将复杂问题分解为若干子问题，通过记录子问题的最优解，避免重复计算，从而高效推导出原问题的解。

我们以01背包问题为例，具象化理解DP的“不重不漏”：

• 问题场景：n个物品，每个物品可选或不选，背包容量为m，求总价值最大。
• 状态定义：dp[j] 表示“背包容量为j时”的最大价值（用一维数组“集中”记录一类状态的最优结果）。
• 状态转移：对第i个物品，决策“选”或“不选”：
  • 不选：dp[j] 保持不变；
  • 选：dp[j] = dp[j - w[i]] + v[i]（从“容量j-w[i]”的状态转移而来）。
• 为什么高效：DP数组没有记录所有具体的物品组合，而是记录“某一容量下的最优价值”，通过状态转移覆盖所有可能的决策，做到“不重不漏”。

二、经典线性DP题型整理

版本1：最大子段和

问题描述：给定一个数组，求其中连续子段的最大和。

核心思路：定义状态记录“以第i个数结尾”的最优解，逐步推导全局最优。

状态定义：dp[i] 表示所有以第i个数结尾的子段中的最大和。

转移方程：dp[i] = max(a[i], dp[i-1] + a[i])（要么从i-1延伸，要么从i重新开始）。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN], dp[MAXN];

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    int ans = a[1];
    dp[1] = a[1]; // 初始化：第一个数结尾的最大和就是它本身
    for (int i = 2; i <= n; i++) {
        dp[i] = max(a[i], dp[i-1] + a[i]); // 状态转移
        ans = max(ans, dp[i]); // 更新全局最大值
    }
    cout << ans << endl;
    return 0;
}

版本2：环形最大子段和

问题描述：数组首尾相连（环形），求其中连续子段的最大和。

核心思路：分两种情况讨论，取最大值：

1. 子段不跨过首尾边界 → 直接求普通最大子段和；
2. 子段跨过首尾边界 → 等价于“数组总和 - 最小子段和”（总和减去中间不选的最小部分）。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN];

// 求普通最大子段和
int maxSub(int n) {
    int dp = a[1], ans = a[1];
    for (int i = 2; i <= n; i++) {
        dp = max(a[i], dp + a[i]);
        ans = max(ans, dp);
    }
    return ans;
}

// 求普通最小子段和
int minSub(int n) {
    int dp = a[1], ans = a[1];
    for (int i = 2; i <= n; i++) {
        dp = min(a[i], dp + a[i]);
        ans = min(ans, dp);
    }
    return ans;
}

int main() {
    int n; cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i]; // 计算数组总和
    }
    
    int maxS = maxSub(n); // 情况1：不跨边界
    int minS = minSub(n); // 用于情况2：跨边界
    cout << max(maxS, sum - minS) << endl; // 两种情况取最大值
    return 0;
}

版本3：最大子矩阵之和

问题描述：给定一个二维矩阵，求其中子矩阵的最大和。

核心思路：

1. 用两层循环枚举子矩阵的“最上行”和“最下行”；
2. 利用二维前缀和思想，将这两行之间的列“压缩”成一维数组；
3. 对压缩后的一维数组求“最大子段和”，即为当前上下行边界下的最优解。

时间复杂度：O(n³)

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 205;
int a[MAXN][MAXN], sum[MAXN]; // sum数组用于“压缩”列

// 求一维数组的最大子段和
int maxSub(int m) {
    int dp = sum[1], ans = sum[1];
    for (int i = 2; i <= m; i++) {
        dp = max(sum[i], dp + sum[i]);
        ans = max(ans, dp);
    }
    return ans;
}

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    int ans = -1e9;
    for (int i = 1; i <= n; i++) { // 枚举子矩阵最上行
        memset(sum, 0, sizeof sum); // 每次更换上行时，重置压缩数组
        for (int j = i; j <= n; j++) { // 枚举子矩阵最下行
            for (int k = 1; k <= m; k++) 
                sum[k] += a[j][k]; // 将第j行的数累加到sum数组，完成“列压缩”
            ans = max(ans, maxSub(m)); // 对压缩后的数组求最大子段和
        }
    }
    cout << ans << endl;
    return 0;
}

版本4：长度至少为k的最大子段和

问题描述：给定数组，求长度≥k的连续子段的最大和。

核心思路：

• 前缀和 s[i]：表示前i项的总和；
• mi[i]：记录 min(s[0], s[1],..., s[i])（前缀和的最小值）；
• 以第i项结尾、长度≥k的最大子段和 = s[i] - mi[i - k]。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN], s[MAXN], mi[MAXN]; // s是前缀和，mi记录前缀和的最小值

int main() {
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i]; // 计算前缀和
    }
    
    mi[0] = s[0];
    for (int i = 1; i <= n; i++) 
        mi[i] = min(mi[i-1], s[i]); // 预处理mi数组
    
    int ans = -1e9;
    for (int i = k; i <= n; i++) // 枚举结尾位置i，长度至少k，所以i从k开始
        ans = max(ans, s[i] - mi[i - k]); // 核心公式
    cout << ans << endl;
    return 0;
}

版本5：选两个不重叠的最大子段和

问题描述：在数组中选两个不重叠的连续子段，求它们的总和最大。

核心思路：

1. 预处理 ma[i]：前i个数中的最大子段和；
2. 预处理 ma2[i]：从第i个数到第n个数的最大子段和；
3. 枚举分割点，计算 ma[i] + ma2[i+1]，取最大值。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN];
int dp[MAXN], ma[MAXN];   // dp[i]以i结尾，ma[i]前i个最大
int dp2[MAXN], ma2[MAXN]; // dp2[i]以i开头，ma2[i]i到n最大

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    // 1. 预处理：从左到右，求前i个的最大子段和
    dp[1] = a[1]; ma[1] = a[1];
    for (int i = 2; i <= n; i++) {
        dp[i] = max(a[i], dp[i-1] + a[i]);
        ma[i] = max(ma[i-1], dp[i]);
    }
    
    // 2. 预处理：从右到左，求i到n的最大子段和
    dp2[n] = a[n]; ma2[n] = a[n];
    for (int i = n-1; i >= 1; i--) {
        dp2[i] = max(a[i], dp2[i+1] + a[i]);
        ma2[i] = max(ma2[i+1], dp2[i]);
    }
    
    // 3. 枚举分割点，取最大值
    int ans = -1e9;
    for (int i = 1; i < n; i++) // 前i个和i+1到n，不重叠
        ans = max(ans, ma[i] + ma2[i+1]);
    cout << ans << endl;
    return 0;
}