线性动态规划经典例题解析

最大子段和

在处理子序列和子数组问题时，定义状态表示有一个技巧：以某个位置为结尾，结合题意来定义。

状态表示

f[i] 表示以 i 位置为结尾的所有子数组中，最大和是多少。

状态转移方程

根据最后一步划分情况。如果 n 为 1，最大子段就是它本身。如果 n 大于 1，第 i 个格子的最大子段和有两种可能：

1. 最大子段和是它本身 a[i]，因为之前的最大子段和可能是负数。
2. 最大子段和是第 i 个格子之前的所有子段中的最大子段加上第 i 个格子的数据。 综合起来：

f[i] = max(a[i], f[i - 1] + a[i]);

初始化与结果

将 f[0] 初始化为 0 即可满足要求。填表顺序从左往右。结果为 f 数组中的最大值。为了节省空间，可以在输入时直接更新 f 数组并维护最大值。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n;
int f[N];

int main() {
    cin >> n;
    // 初始化
    f[0] = 0;
    int ret = -0x3f3f3f3f;
    // 按序填表 + 更新 ret
    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;
}

传球游戏

题目规定所有同学站成一个圆圈，球可能从左边格子来也可能从右边格子来。需要知道该格子编号和传球次数，因此使用二维数组 f[i][j]。

状态表示

f[i][j] 表示球传递了 i 次之后，最终落在了 j 号同学手里一共有多少种方案。

状态转移方程

由于是环形结构，需要分三种情况讨论：

1. 接受球的是编号为 1 的同学，来源可能是 2 和 n。 dp[i][1] = dp[i - 1][2] + dp[i - 1][n]
2. 接受球的是编号为 2 到 n-1 的同学 j，来源可能是 j-1 和 j+1。 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
3. 接受球的是编号为 n 的同学，来源可能是 1 和 n-1。 dp[i][n] = dp[i - 1][1] + dp[i - 1][n - 1]

初始化与填表

第一行表示传球次数为 0，此时球在一号同学手里，所以 dp[0][1] = 1。填表顺序从上往下依次填每一行。最终结果是 dp[m][1]。

#include <iostream>
using namespace std;
const int N = 40;
int n, m;
int dp[N][N];

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];
        // 填第 2 到 n-1 个同学
        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 卡片 i 张、2 卡片 j 张、3 卡片 k 张、4 卡片 z 张的情况下的最大分数。虽然本质涉及五维信息，但一维数组下标 x 可以通过另外 4 个变量计算出来：x = 1 + i + 2*j + 3*k + 4*z。因此使用四维 dp 数组存储。

状态转移方程

走到 x 一共有四种可能：分别是从 x-1 到 x、x-2 到 x、x-3 到 x、x-4 到 x。对应消耗不同种类的卡片。 例如从 x-1 过来，消耗一张 1 卡片，状态为 dp[i-1][j][k][z]。 注意边界条件，访问 dp[i-1] 时需保证 i > 0。

t = max(t, dp[i - 1][j][k][z] + a[x]);

同理处理其他三种卡片。

初始化与填表

题目规定乌龟棋子自动获得起点格子的分数，所以 dp[0][0][0][0] = a[1]。 代码实现中用 4 个 for 循环依次枚举 i, j, k, z 的所有取值，取出最大值作为当前状态的取值。最终结果是 dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]]。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 360;
const int M = 50;
int n, m;
int a[N], cnt[5], dp[M][M][M][M];

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 x = 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[x]);
                    if (j > 0) t = max(t, dp[i][j - 1][k][z] + a[x]);
                    if (k > 0) t = max(t, dp[i][j][k - 1][z] + a[x]);
                    if (z > 0) t = max(t, dp[i][j][k][z - 1] + a[x]);
                }
            }
        }
    }
    cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;
    return 0;
}