动态规划入门：线性 DP 四道经典题解析

最大子段和

题目描述

给定一个整数序列，找出连续子序列的最大和。

思路分析

定义 f[i] 为以第 i 个元素结尾的所有子数组中，最大的和是多少。这个定义非常关键，它锁定了'结尾'位置，从而避免了重复计算。

对于第 i 个元素，有两种选择：

1. 接在前面的子段后面：f[i-1] + a[i]
2. 重新开始一个新的子段：a[i]

如果前面的子段和是负数，加上它只会让当前值变小，所以直接选 a[i] 更好。状态转移方程即为：f[i] = max(a[i], f[i-1] + a[i])。

初始化时，设 f[0] = 0 即可满足逻辑。最终答案不是 f[n]，而是整个 f 数组中的最大值。

为了节省空间，我们可以边读入边计算，不需要额外存储原数组 a。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2e5 + 10;
int n;
int f[N];

int main() {
    cin >> n;
    
    // 初始化 f[0] 为 0
    f[0] = 0;
    
    int ret = -0x3f3f3f3f; // 初始化为极小值
    
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        f[i] = max(x, x + f[i - 1]);
        ret = max(ret, f[i]);
    }
    
    cout << ret << endl;
    return 0;
}

传球游戏

题目描述

n 个同学围成一圈，球从 1 号同学开始传，传 m 次后回到 1 号同学的方案数。

思路分析

这是一个环形结构的问题，用二维 DP 比较直观。定义 dp[i][j] 表示传了 i 次球后，球在 j 号同学手里的方案数。

因为是在圆圈上，每个同学只能从左边的邻居或右边的邻居接球。对于编号 j，来源可能是 j-1 和 j+1。但要注意首尾相接的特殊情况：

• 1 号同学的左边是 n 号，右边是 2 号。
• n 号同学的左边是 n-1 号，右边是 1 号。

初始化时，dp[0][1] = 1，表示 0 次传球时球在 1 号手里。其他 dp[0][j] 均为 0。

填表顺序是先枚举传球次数 i，再枚举同学编号 j。注意处理边界时的索引映射。

#include <iostream>
using namespace std;

const int N = 40;
int n, m;
int dp[N][N]; // dp[次数][同学编号]

int main() {
    cin >> n >> m;
    
    // 初始化：0 次传球在 1 号手中
    dp[0][1] = 1;
    
    // 枚举传球次数
    for (int i = 1; i <= m; i++) {
        // 处理 1 号同学（特殊边界）
        dp[i][1] = dp[i - 1][2] + dp[i - 1][n];
        
        // 处理中间同学
        for (int j = 2; j < n; j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
        }
        
        // 处理 n 号同学（特殊边界）
        dp[i][n] = dp[i - 1][1] + dp[i - 1][n - 1];
    }
    
    cout << dp[m][1] << endl;
    return 0;
}

乌龟棋

题目描述

棋盘是一维的，有若干张卡片（1~4 步）。从起点出发，用完所有卡片到达终点，求路径上的最大分数。

思路分析

这道题看起来像背包问题，但状态维度较高。我们需要知道每种卡片的剩余数量来决定下一步怎么走。不过，既然卡片总数固定，我们可以反过来思考：用了多少张 1 步卡、2 步卡... 就能确定当前所在的位置。

定义 dp[i][j][k][z] 表示使用了 i 张 1 步卡、j 张 2 步卡、k 张 3 步卡、z 张 4 步卡时的最大得分。当前位置可以通过公式计算：pos = 1 + i1 + j2 + k3 + z4。

状态转移时，考虑最后一步是从哪里来的。比如当前状态是 (i,j,k,z)，最后一步如果是用了 1 步卡，那么前一个状态就是 (i-1,j,k,z)。我们需要遍历四种可能的来源，取最大值。

注意边界条件：只有当对应卡片数量大于 0 时，才能进行相应的状态转移。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 360;
const int M = 50;

int n, m;
int a[N];       // 棋盘分数
int cnt[5];     // 卡片数量统计
int dp[M][M][M][M]; // 四维 DP 数组

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    while (m--) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    
    // 初始化：起点分数
    dp[0][0][0][0] = a[1];
    
    // 四层循环枚举卡片使用数量
    for (int i = 0; i <= cnt[1]; i++) {
        for (int j = 0; j <= cnt[2]; j++) {
            for (int k = 0; k <= cnt[3]; k++) {
                for (int z = 0; z <= cnt[4]; z++) {
                    // 计算当前位置
                    int pos = 1 + i + 2 * j + 3 * k + 4 * z;
                    int &t = dp[i][j][k][z];
                    
                    // 尝试从不同方向转移
                    if (i > 0) t = max(t, dp[i - 1][j][k][z] + a[pos]);
                    if (j > 0) t = max(t, dp[i][j - 1][k][z] + a[pos]);
                    if (k > 0) t = max(t, dp[i][j][k - 1][z] + a[pos]);
                    if (z > 0) t = max(t, dp[i][j][k][z - 1] + a[pos]);
                }
            }
        }
    }
    
    cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;
    return 0;
}

以上四道题涵盖了线性 DP 中一维、二维及多维状态压缩的典型场景。掌握状态定义的切入点，往往比死记硬背模板更重要。