线性动态规划：四道经典例题实战解析 | 极客日志

C++算法

线性动态规划：四道经典例题实战解析

线性动态规划是算法基础，状态转移依赖前序状态。通过台阶、最大子段和、传球游戏、乌龟棋四题，演示一维至多维状态设计。涵盖模运算防溢出、负数处理、环形边界及四维状态压缩技巧，提供完整 C++ 实现与思路分析。

咸鱼开飞机发布于 2026/3/28更新于 2026/4/264 浏览

线性动态规划：四道经典例题实战解析

概述

线性动态规划（Linear DP）是算法入门中最基础且常见的一类问题。其核心特征是状态转移仅依赖于前一个或前几个状态，状态间呈线性关系，通常可用一维或二维数组存储。

本文通过四道经典例题，从一维到多维逐步深入，演示如何构建状态、推导转移方程以及处理边界条件。代码均使用 C++ 实现，注重逻辑清晰与工程实践。

台阶问题

题目描述

有 N 个台阶，每次可以走 1 到 K 步，求走到第 N 个台阶的方案数。结果对 100003 取模。

解题思路

这道题本质上是斐波那契数列的推广。我们定义 dp[i] 为走到第 i 个台阶的方案数。

状态转移 到达第 i 个台阶，可以从 i-1, i-2, ..., i-k 处跳过来。因此方案数是这些位置方案数的总和。
```
dp[i] = (dp[i-1] + dp[i-2] + ... + dp[i-k]) % MOD
```
注意数据范围较大，累加过程中需随时取模防止溢出。同时要注意下标不能越界，当 i-j < 0 时停止循环。
初始化技巧 很多初学者会尝试手动初始化前 k 个状态，但这比较繁琐。更优雅的做法是将 dp[0] 设为 1。这代表站在起点（第 0 阶）有一种方案（不动），这样从 dp[1] 开始递推时，逻辑自然统一。
填表顺序 从左往右依次计算即可。

参考实现

#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 = ; j <= k; j++) {
             (i - j < ) ; 
            dp[i] = (dp[i] + dp[i - j]) % MOD;
        }
    }
    
    cout << dp[n] << endl;
     ;
}

状态定义 定义 f[i] 为以第 i 个元素结尾的所有子数组中，最大的和是多少。这样定义的好处是，我们在计算 f[i] 时，只需要考虑前一个状态 f[i-1]。
状态转移 对于第 i 个元素 a[i]，有两种选择：
- 接在前面的子段后面：f[i-1] + a[i]
- 重新开始一个新的子段：a[i]
如果前面的子段和是负数，加上它只会变小，所以不如直接舍弃前面部分，从当前元素开始。因此转移方程为：
```
f[i] = max(a[i], f[i-1] + a[i])
```
初始化与结果 将 f[0] 初始化为 0 即可满足递推。最终答案不是 f[n]，而是整个 f 数组中的最大值，因为最大子段不一定以最后一个元素结尾。
空间优化 由于 f[i] 只依赖 f[i-1]，我们可以省略 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;
}

#include <iostream>
using namespace std;

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

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];
        
        // 处理中间同学
        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;
int a[N];       // 棋盘分数
int cnt[5];     // 卡片数量统计
int dp[M][M][M][M]; // 四维 DP 数组

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 * 1 + j * 2 + k * 3 + z * 4;
                    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;
}