跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客工具镜像开源精选AI社区
我的书AI 学习话题UI配色美学关于
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C++算法

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

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

zhang发布于 2026/3/22更新于 2026/11/14101 浏览
线性动态规划经典四题详解:台阶、最大子段和、传球游戏与乌龟棋

线性动态规划简介

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

台阶问题

题目描述

(题目图片已移除)

题目解析

  1. 状态表示 dp[i] 表示走到第 i 个台阶的所有方案数。

  2. 状态转移方程 第 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)。

  3. 初始化 直接将 dp[0] 置为 1 即完成初始化操作,然后从 dp[1] 开始往后循环计算方案数。

  4. 填表顺序 从左往右。

  5. 输出结果 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;
    return 0;
}

最大子段和

题目描述

(题目图片已移除)

题目解析

  1. 状态表示 以某个位置为结尾,结合题意来定义状态表示。f[i] 表示以 i 位置为结尾的所有子数组中,最大和是多少。

  2. 状态转移方程 首先明确本题数据是从数组下标 1 开始存储的。如果 n 为 1,也就是只有一个数据,那么最大子段就是它本身,所以 f[i] = a[i]。 如果 n 大于 1,第 i 个格子的最大子段和有两种可能: 第一,最大子段和是它本身 a[i],因为第 i 个格子之前的最大子段和可能是负数。 f[i] = a[i] 第二,最大子段和是第 i 个格子之前的所有子段中的最大子段加上第 i 个格子的数据。 f[i] = f[i - 1] + a[i] 总的来说第 i 个格子的最大子段和就是两种可能中取较大值: f[i] = max(a[i], f[i - 1] + a[i])

  3. 初始化 当填第一个格子 f[1] 时,根据状态转移方程:f[1] = max(a[1], f[0] + a[1]),而根据我们之前的分析,第一个格子的值就是它本身:f[i] = a[i],所以只要我们把 f[0] 初始化为 0,即可满足要求。

  4. 填表顺序 从左往右。

  5. 输出结果 结果为 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;
    // 按序填表 + 更新 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;
}

传球游戏

题目描述

(题目图片已移除)

题目解析

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

  2. 状态转移方程 本题推导状态转移方程需要分类讨论,因为题目规定同学围成一个圈,但是我们要用二维线性数组存储数据,所以需要分三种情况: 第一种是接受球的是编号为 1 的同学,此时传递球的同学编号可能是 2 和 n,所以编号为 1 的同学的传球方案数就是 2 和 n 同学的方案数之和: dp[i][1] = dp[i - 1][2] + dp[i - 1][n] 第二种是接受球的是编号为从 2 到 n - 1 的同学,假设为 j,此时传递球的同学编号可能是 j - 1 和 j + 1,所以编号为 1 的同学的传球方案数就是 j - 1 和 j + 1 同学的方案数之和: dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] 第三种是接受球的是编号为 n 的同学,此时传递球的同学编号可能是 1 和 n - 1,所以编号为 n 的同学的传球方案数就是 1 和 n - 1 同学的方案数之和: dp[i][n] = dp[i - 1][1] + dp[i - 1][n - 1]

  3. 初始化 f[0][1] = 1

  4. 填表顺序 从上往下依次填每一行。

  5. 输出结果 f[m][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;
}

乌龟棋

题目描述

(题目图片已移除)

题目解析

  1. 状态表示 本题 dp 数组每个格子要存储六个信息:走到 x 格子时,用 1 卡片 i 张、用 2 卡片 j 张、用 3 卡片 k 张、用 4 卡片 z 张的情况下的最大分数。所以我们用一个四维 dp 数组存储,需要用到 x 时通过另外 4 个变量计算得到。 x = 1 + i + 2 * j + 3 * k + 4 * z

  2. 状态转移方程 推导状态转移方程本质就是推导 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] 的取值。

  1. 初始化 题目规定乌龟棋子自动获得起点格子的分数,所以 dp[0][0][0][0] = a[1]

  2. 输出结果 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;
}

目录

  1. 线性动态规划简介
  2. 台阶问题
  3. 题目描述
  4. 题目解析
  5. 代码
  6. 最大子段和
  7. 题目描述
  8. 题目解析
  9. 代码
  10. 传球游戏
  11. 题目描述
  12. 题目解析
  13. 代码
  14. 乌龟棋
  15. 题目描述
  16. 题目解析
  17. 代码

更多推荐文章

查看全部
  • JDK 下载、安装与环境变量配置图文教程
  • Windows 系统下 Neo4j 与 JDK 安装配置实战
  • Python 之父 Guido Van Rossum 宣布从 Dropbox 退休
  • 开源 AI 编程工具选型对比:OpenCode 与 GitHub Copilot
  • VR 科普学习机赋能新课堂
  • C++ 运算符重载:自定义类型的运算扩展
  • 前端交互式 3D 人体肌肉解剖图:Three.js + React Three Fiber 实战
  • 搞懂 HTML、CSS 和 JavaScript 的分工关系
  • ChatMed 开源中文医疗大模型介绍与对比分析
  • Python Web 框架 Django 实战指南
  • Seedance 2.0 双分支扩散 Transformer 解析
  • Redis 单线程服务器如何实现高性能及源码剖析
  • Python 入门教程:环境搭建、基础语法与数据类型详解
  • Claude Code 从部署到项目实战详解
  • 数据结构基础:二叉树与堆的实现详解
  • 哈希表实战:四数相加、赎金信与三/四数之和解法
  • APK 反编译基础与静态分析方法详解
  • Java Map 常用方法与核心实现类详解
  • LlamaIndex 安装与配置:本地模型集成指南
  • 数据结构:八种常见排序算法详解

相关免费在线工具

  • 加密/解密文本

    使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online

  • Gemini 图片去水印

    基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online

  • Markdown转HTML

    将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online

  • HTML转Markdown

    将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online