线性动态规划经典四题详解：台阶、最大子段和、传球游戏与乌龟棋 | 极客日志

C++算法

线性动态规划经典四题详解：台阶、最大子段和、传球游戏与乌龟棋

线性动态规划状态转移依赖前序状态，常用一维或二维数组存储。涵盖台阶问题（多步跳跃）、最大子段和（连续子序列最优解）、传球游戏（环形状态转移）及乌龟棋（多维资源分配）。通过定义状态、推导方程、初始化及填表顺序，解决典型 DP 模型。代码采用 C++ 实现，包含边界处理与空间优化技巧。

zhang发布于 2026/3/22更新于 2026/5/912 浏览

线性动态规划经典四题详解：台阶、最大子段和、传球游戏与乌龟棋

线性动态规划简介

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

台阶问题

题目描述

（题目图片已移除）

题目解析

状态表示 dp[i] 表示走到第 i 个台阶的所有方案数。
状态转移方程第 i 个台阶的方案数等于从 i-1 阶到 i-k 阶的所有方案数之和。因为本题数据比较大，用 long long 都无法保证数据不越界，所以题目规定方案数还需要模 100003。第 i 个台阶的方案数等于从 i-1 阶到 i-k 阶的所有方案数之和再模上 100003。注意可能越界访问，比如 i 为 3，k 为 10，i-k 是可能访问到数组负下标的，所以访问台阶时需要保证 i-k 始终大于等于 0。 dp[i] = (dp[i] + dp[i - j]) % 100003（j 从 1 到 k）。
初始化直接将 dp[0] 置为 1 即完成初始化操作，然后从 dp[1] 开始往后循环计算方案数。
填表顺序从左往右。
输出结果 dp[n] 即为结果。

代码

#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;
    // 循环填表
    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;
     ;
}

#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;
    // 按序填表 + 更新 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;
}

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

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