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

线性动态规划入门

线性 DP 是动态规划中最基础且常见的一类问题。其核心特点是状态转移只依赖于前一个或前几个状态，状态之间的关系呈线性，通常可以用一维或二维数组来存储。

台阶问题

题目背景 给定 n 个台阶，每次可以走 1 到 k 步，求走到第 n 个台阶的方案数。结果需对 100003 取模。

思路解析 这是经典的递推模型。我们定义 dp[i] 为走到第 i 个台阶的方案总数。

1. 状态转移：要到达第 i 阶，可以从 i-1, i-2, ..., i-k 阶跳上来。因此 dp[i] 等于这 k 个位置方案数的总和。注意数据范围较大，计算过程中需要取模，且需防止访问负下标（即保证 i-j >= 0）。

   dp[i] = (dp[i] + dp[i - j]) % MOD; // j 从 1 到 k
   

2. 初始化技巧：与其麻烦地初始化前 k 个元素，不如将 dp[0] 设为 1。这代表站在起点有一种方案（不动），这样从 dp[1] 开始循环即可自然推导后续值。
3. 填表顺序：从小到大遍历 i。

代码实现

#include <iostream>
using namespace std;

const int N = 1e5 + 10, MOD = 1e5 + 3;
int n, k;
long long dp[N];

int main() {
    cin >> n >> k;
    
    // 初始化：起点视为一种方案
    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;
}

最大子段和

题目背景 给定一个整数序列，找出连续子段的最大和。

思路解析 这里推荐一种针对子序列/子数组问题的通用状态定义技巧：以某个位置为结尾。

1. 状态定义：f[i] 表示以第 i 个元素结尾的所有子数组中，最大的和是多少。
2. 状态转移：对于第 i 个元素，有两种选择：
   • 接在前面的子段后面：f[i-1] + a[i]
   • 重新开始一个新的子段：a[i]（如果前面的和是负数，加了反而变小） 取两者最大值：f[i] = max(a[i], f[i-1] + a[i])。
3. 初始化：f[0] 设为 0，这样第一个元素 f[1] 就能正确通过公式计算得出。
4. 结果：遍历整个 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 数组，边读边算即可。

传球游戏

题目背景 n 个人围成一圈，球从 1 号开始传 m 次，问最后回到 1 号的方案数。

思路解析 这是一个典型的环形 DP 问题，需要记录传递次数和当前持球人。

1. 状态定义：dp[i][j] 表示球传递了 i 次后，落在第 j 个人手里的方案数。
2. 状态转移：由于是环形，每个人只能从左边或右边的人接到球。
   • 1 号同学：可能来自 2 号和 n 号。
   • 中间同学 j：可能来自 j-1 和 j+1。
   • n 号同学：可能来自 1 号和 n-1。 方程形式类似：dp[i][j] = dp[i-1][left] + dp[i-1][right]。
3. 初始化：dp[0][1] = 1，表示 0 次传球时在 1 号手里。其他初始化为 0。
4. 填表顺序：先枚举传球次数 i，再枚举人数 j。

代码实现

#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];
        
        // 处理中间人员
        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. 状态定义：dp[i][j][k][z] 表示使用了 i 张 1 步卡、j 张 2 步卡、k 张 3 步卡、z 张 4 步卡时的最大分数。 当前位置可以通过公式推算：pos = 1 + i + 2*j + 3*k + 4*z。
2. 状态转移：到达当前状态，可能是由少用一张某种卡片的状态转移而来。例如，用了 i 张 1 步卡，可能是从 dp[i-1][j][k][z] 加上当前格子的分数得到的。 需要判断边界，确保不越界访问（如 i>0 才能从 i-1 转移）。
3. 初始化：dp[0][0][0][0] = a[1]，起点分数。
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 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 的核心套路。多动手写几遍代码，体会状态定义和转移方程的设计过程，比单纯背模板更有用。