线性 DP 经典四题详解：台阶、子段和、传球与乌龟棋

2. 最大子段和 (P1115)

题目描述

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

解题思路

处理子序列或子数组问题时，一个常用的技巧是：以某个位置为结尾来定义状态。

状态定义 f[i] 表示以第 i 个位置结尾的所有子数组中，最大的和是多少。

状态转移 对于第 i 个数 a[i]，有两种选择：

1. 它自己作为一个新的子段开头：f[i] = a[i]
2. 接在前面的子段后面：f[i] = f[i-1] + a[i]

取两者中的较大值即可：f[i] = max(a[i], f[i-1] + a[i])。

初始化 根据方程，f[1] = max(a[1], f[0] + a[1])。为了让第一个元素直接等于自身，我们将 f[0] 初始化为 0。

输出结果 最终答案是 f 数组中的最大值，因为最大子段不一定以最后一个元素结尾。

代码实现

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

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

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 初始化
    f[0] = 0;
    
    // 按序填表
    for (int i = 1; i <= n; i++) {
        f[i] = max(a[i], a[i] + f[i - 1]);
    }
    
    // 找最大值
    int ret = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        ret = max(ret, f[i]);
    }
    cout << ret << endl;
    return 0;
}

优化提示：如果不需要保留原数组，可以在输入时直接计算 f[i]，节省空间。

3. 传球游戏 (P1057)

题目描述

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

解题思路

这是一个典型的环形结构 DP 问题。由于涉及'次数'和'当前持有者'，我们需要二维状态。

状态定义 f[i][j] 表示球传递了 i 次后，落在第 j 个同学手里的方案数。

状态转移 因为是圆圈，第 j 个同学可能从 j-1 或 j+1 接到球。需要注意首尾相接的情况：

• 1 号同学：只能从 2 号和 n 号传来。
• n 号同学：只能从 1 号和 n-1 号传来。
• 中间同学 j：从 j-1 和 j+1 传来。

初始化 f[0][1] = 1，表示 0 次传球时球在 1 号手里，方案数为 1。其他 f[0][j] 默认为 0。

代码实现

#include <iostream>
using namespace std;

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

int main() {
    cin >> n >> m;
    
    // 初始化
    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;
}

4. 乌龟棋 (P1541)

题目描述

棋盘是一维的，有四种卡片（1~4 步），每种卡片数量有限。求从起点走到终点的最大分数。

解题思路

这题的状态维度较高。我们需要知道每种卡片的剩余使用数量，以及当前位置。

状态定义 虽然直觉上需要记录位置 x，但位置其实可以由卡片的使用情况推导出来： x = 1 + i*1 + j*2 + k*3 + z*4 因此，我们可以用四维数组 dp[i][j][k][z]，分别表示使用了 i 张 1 步卡、j 张 2 步卡、k 张 3 步卡、z 张 4 步卡时的最大分数。

状态转移 到达当前状态 (i, j, k, z)，最后一步可能是用了任意一种卡片。我们需要比较四种来源的最大值：

• 用了一张 1 步卡：来自 dp[i-1][j][k][z]
• 用了一张 2 步卡：来自 dp[i][j-1][k][z]
• ...

边界处理 在访问 dp[i-1]... 等状态前，必须确保对应的索引大于 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 的一维、二维及多维状态压缩的典型模式。掌握这些基础模型，有助于解决更复杂的动态规划问题。