线性动态规划经典四题实战解析

最大子段和

题目描述：

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

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

推导状态转移方程时，我们根据最后一步来划分情况。如果 n 为 1，也就是只有一个数据，那么最大子段就是它本身，即 f[i] = a[i]。如果 n 大于 1，第 i 个格子的最大子段和有两种可能：

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

总的来说，第 i 个格子的最大子段和就是两种可能中取较大值：f[i] = max(a[i], f[i - 1] + a[i])。

初始化时，当填第一个格子 f[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;
}

这里还有一个优化版本，不需要额外存储 a 数组：

// 优化版（无 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;
    // 按序填表 + 更新 ret
    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;
}

传球游戏

题目描述：

首先要明确某个格子中的信息是从第一个格子开始到该格子一共有多少种方案。分析该格子应该包含哪些信息：因为题目规定所有同学站成一个圆圈，球可能从左边格子来也可能从右边格子来，要传递球所以必然需要知道该格子编号和左边、右边格子的编号。此外还有一个条件：传球次数，所以需要知道球传递了多少次后落在了谁手里。因此我们需要用一个二维数组 f[i][j]。

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

由于同学围成一个圈，但我们要用二维线性数组存储数据，所以需要分三种情况讨论：

1. 接受球的是编号为 1 的同学，此时传递球的同学编号可能是 2 和 n，所以编号为 1 的同学的传球方案数就是 2 和 n 同学的方案数之和：dp[i][1] = dp[i - 1][2] + dp[i - 1][n]。
2. 接受球的是编号为从 2 到 n - 1 的同学，假设为 j，此时传递球的同学编号可能是 j - 1 和 j + 1，所以编号为 j 的同学的传球方案数就是 j - 1 和 j + 1 同学的方案数之和：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]。
3. 接受球的是编号为 n 的同学，此时传递球的同学编号可能是 1 和 n - 1，所以编号为 n 的同学的传球方案数就是 1 和 n - 1 同学的方案数之和：dp[i][n] = dp[i - 1][1] + dp[i - 1][n - 1]。

代码实现上，从上往下按顺序一行一行的填，行表示传球次数，列表示同学编号。第一行表示传球次数为 0，此时根据题目规定球在一号同学手里，dp[0][1] 就表示球传递了 0 次最后落在 1 号同学手里一共有多少种方案。对于这类求方案数的情况，因为一般情况状态转移方程都是累加的，所以一般会将初始情况初始化为 1，即 dp[0][1] = 1。

#include <iostream>
using namespace std;

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

int main() {
    cin >> n >> m;
    // 初始化
    dp[0][1] = 1;
    // 按序填表
    // 从 1 开始枚举传递次数（枚举行）
    for (int i = 1; i <= m; i++) {
        // 填第 1 个同学
        dp[i][1] = dp[i - 1][2] + dp[i - 1][n];
        // 填第 2 到 n-1 个同学
        // 从 2 开始枚举同学编号（枚举列）
        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;
}

乌龟棋

题目描述：

本题有点像飞行棋，投骰子决定走多少步，一共有 6 种情况（1-6 步），本题是抽卡片决定走多少步，一共有 4 种情况（1-4 步），并且本题格子是一维的，走到某个格子即可得到该格子的分数，题目要求我们找出从起点走到终点格子的最大分数。

状态表示方面，本题 dp 数组每个格子要存储六个信息：走到 x 格子时，用 1 卡片 i 张、用 2 卡片 j 张、用 3 卡片 k 张、用 4 卡片 z 张的情况下的最大分数。虽然看起来需要五维数组，但其实一维数组下标 x 可以通过另外 4 个变量计算出来，因为走到 x 格子本质是从下标 1 开始，用了 i 张 1 卡片、j 张 2 卡片、k 张 3 卡片、z 张 4 卡片后走到的位置：x = 1 + i + 2 * j + 3 * k + 4 * z。所以我们用一个四维 dp 数组存储，需要用到 x 时通过另外 4 个变量计算得到。

状态转移方程本质就是推导 dp[i][j][k][z]。根据前面的分析，dp[i][j][k][z] 对应的一维数组下标是 x，那么走到 x 一共有四种可能：分别是从 x-1 到 x、x-2 到 x、x-3 到 x、x-4 到 x。对于 x-1 来说，它对应的 dp 数组是 dp[i - 1][j][k][z]，同理对于 x-2 来说，dp 数组是 dp[i][j - 1][k][z]……

这里有个细节，需要处理边界情况。对于变量 i, j, k, z 来说，它们表示抽取各自卡的张数，对 i 来说，取值范围是从 0 到 cnt[1]，对于 j 来说，取值范围是从 0 到 cnt[2]，k, z 同理。所以 i, j, k, z 取值是非负的，所以要访问 dp[i - 1][j][k][z] 时需要保证 i 大于 0，要访问 dp[i][j - 1][k][z] 时需要保证 j 大于 0，k, z 同理。

状态转移方程如下所示，本质上我们上面的推导是基于最后一步分析的： dp[i][j][k][z] = max(dp[i - 1][j][k][z], dp[i][j - 1][k][z], dp[i][j][k - 1][z], dp[i][j][k][z - 1]) + a[x]

在代码实现中会用 4 个 for 循环依次枚举 i, j, k, z 的所有取值，枚举一种 i, j, k, z 的取值情况就会将四种可能的状态转移方程作比较，取出最大值作为 dp[i][j][k][z] 的取值。

初始化时，题目规定乌龟棋子自动获得起点格子的分数，所以 dp[0][0][0][0] = a[1]。输出结果为 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; // 存储棋盘 存储四张卡片各自数目 dp 数组
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 = 0;
        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++) {
                    // x 为当前访问格子下标（数组 a 下标）
                    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;
}