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

线性动态规划入门

线性 DP 是动态规划问题中最基础、最常见的一类。它的特点是状态转移只依赖于前一个或前几个状态，状态之间的关系是线性的，通常可以用一维或者二维数组来存储状态。我们在入门阶段解决的《下楼梯》以及《数字三角形》其实都是线性 DP，一个是一维的，另一个是二维的。

台阶问题

题目描述

思路解析

这道题可以看作是下楼梯问题的加强版，总体思路不变。我们按照动态规划的常规步骤来分析。

首先定义状态，dp[i] 表示走到第 i 个台阶的所有方案数。接下来推导状态转移方程，第 i 个台阶的方案数等于从 i-1 阶到 i-k 阶的所有方案数之和。因为本题数据比较大，用 long long 都无法保证数据不越界，所以题目规定方案数还需要模 100003。注意访问台阶时需要保证 i-k 始终大于等于 0，防止负下标越界。

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, MOD = 1e5 + 3;
int n, k;
LL dp[N];

int main() {
    cin >> n >> k;
    // 初始化：将 dp[0] 置为 1，相当于起点有一种方案
    dp[0] = 1;
    // 循环填表
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            // 保证不越界访问
            if (i - j < 0) break;
            dp[i] = (dp[i] + dp[i - j]) % MOD;
        }
    }
    // 输出结果
    cout << dp[n] << endl;
    return 0;
}

关于初始化，大家可能会想到先将数组前 k 个数据初始化，但这样操作比较麻烦。这里介绍一个新方法，直接将 dp[0] 置为 1 即可完成初始化操作，然后从 dp[1] 开始往后循环计算方案数即可。

最大子段和

题目描述

思路解析

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

对于本题，f[i] 表示以 i 位置为结尾的所有子数组中，最大和是多少。推导状态转移方程时，我们根据最后一步来划分情况。如果 n 为 1，最大子段就是它本身。如果 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 数组存储输入，可以在读入时直接处理：

#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;
    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]

填表顺序是从上往下依次填每一行，行表示传球次数，列表示同学编号。初始化时，dp[0][1] = 1，表示球一开始在 1 号同学手里，传递 0 次有 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;
}

乌龟棋

题目描述

思路解析

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

状态表示上，dp[i][j][k][z] 表示用到 1 卡片 i 张、2 卡片 j 张、3 卡片 k 张、4 卡片 z 张时的最大分数。虽然看起来像五维（包含当前坐标），但其实一维数组下标 x 可以通过另外 4 个变量计算出来：x = 1 + i + 2*j + 3*k + 4*z。

状态转移方程本质是推导 dp[i][j][k][z]，走到当前位置 x 一共有四种可能：分别是从 x-1 到 x、x-2 到 x、x-3 到 x、x-4 到 x。对应的状态分别是 dp[i-1][j][k][z]、dp[i][j-1][k][z] 等。需要注意边界情况，访问 dp[i-1]... 时需要保证 i > 0。

初始化时，乌龟棋子自动获得起点格子的分数，所以 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;
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 为当前访问格子下标
                    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;
}