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

最大子段和

题目描述

给定一个整数序列，找出一个连续子段，使得该子段的元素和最大。

解题思路

在处理子序列或子数组问题时，定义状态的关键在于结合题意确定'以谁结尾'。

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

状态转移 考虑最后一步的情况：对于第 i 个格子，最大子段和有两种可能：

1. 它自己单独构成一段，即 f[i] = a[i]。这通常发生在之前的累积和为负数时。
2. 接在前面的最大子段后面，即 f[i] = f[i - 1] + a[i]。

综合这两种情况，取最大值即可：f[i] = max(a[i], f[i - 1] + a[i])。

初始化与结果 当 i=1 时，根据方程 f[1] = max(a[1], f[0] + a[1])，若将 f[0] 初始化为 0，则逻辑自洽。最终答案不是 f[n]，而是整个 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]);
    }
    
    // 输出结果：f 数组中的最大值
    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;
    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;
}

传球游戏

题目描述

n 个同学站成一个圆圈，球从 1 号同学开始传递，共传 m 次，问球回到 1 号同学的方案数。

解题思路

这是一个典型的环形结构 DP 问题。由于球可能从左邻也可能从右邻传来，我们需要记录当前的传球次数和持球人的编号。

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

状态转移 因为围成圆圈，需要分情况讨论边界：

1. 1 号同学：只能从 2 号和 n 号同学处接球。dp[i][1] = dp[i-1][2] + dp[i-1][n]
2. 中间同学 (2 到 n-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。此时球在 1 号同学手中，方案数为 1。所以 dp[0][1] = 1，其余为 0。

填表顺序 从上往下依次填每一行（枚举传球次数），每行内从左往右（枚举同学编号）。

代码实现

#include<iostream>
using namespace std;

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

int main() {
    cin >> n >> m;
    
    // 初始化：0 次传球在 1 号同学手里
    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、2、3、4 步），每种卡片数量有限。求从起点走到终点能获得的最大分数。

解题思路

本题类似于飞行棋，但决策维度更多。我们需要知道每种卡片的剩余使用数量来确定当前位置。

状态定义 虽然棋盘是一维的，但决定当前位置的是四种卡片的消耗量。设 dp[i][j][k][z] 表示使用了 i 张 1 步卡、j 张 2 步卡、k 张 3 步卡、z 张 4 步卡时的最大分数。

当前位置 x 可以通过公式计算：x = 1 + i + 2j + 3k + 4*z。

状态转移 到达当前状态 (i, j, k, z) 的前一步可能是使用了某一张卡片。例如，如果 i > 0，则上一步可能是 (i-1, j, 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] ) + score[x]

注意处理边界，只有当对应卡片数量大于 0 时才能进行转移。

初始化 题目规定自动获得起点分数，所以 dp[0][0][0][0] = a[1]。

代码实现

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

const int N = 360;
const int M = 50;

int n, m;
int a[N], cnt[5]; // 存储棋盘分数，存储四张卡片各自数目
int 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++) {
                    // 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;
}

总结

这四道题涵盖了线性 DP 从一维到多维的典型应用场景。掌握它们的关键在于准确理解状态的含义，并找到正确的'最后一步'来划分情况。在实际编码中，务必注意数组越界、初始化细节以及取模运算的时机。