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

线性 DP 概述

线性动态规划是算法基础中最常见的一类问题。其核心特点是状态转移只依赖于前一个或前几个状态，状态之间的关系呈线性，通常可用一维或二维数组存储。我们在入门阶段解决的《下楼梯》以及《数字三角形》其实都属于线性 DP，分别对应一维和二维的情况。

下面通过四道经典题目，从状态定义、转移方程到代码实现，系统梳理线性 DP 的解题思路。

台阶问题

题目描述

解题思路

本题可以看作是《下楼梯》问题的加强版。我们按照动态规划的常规步骤来分析：

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

2. 状态转移方程 第 i 个台阶的方案数等于从 i-1 阶到 i-k 阶的所有方案数之和。由于数据量较大，结果需要对 100003 取模。注意边界检查，当 i-j < 0 时需停止循环，避免负下标访问。

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

3. 初始化 直接令 dp[0] = 1 即可。这相当于站在起点（第 0 阶）有一种方案（不动），后续计算会自动累加。

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;
    
    // 初始化：站在第 0 阶算作一种方案
    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] = a[i]
   • 接在前面的子段后面：f[i] = f[i - 1] + 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;
    int ret = -0x3f3f3f3f;
    
    for (int i = 1; i <= n; i++) {
        f[i] = max(a[i], a[i] + f[i - 1]);
        ret = max(ret, f[i]);
    }
    
    cout << ret << endl;
    return 0;
}

优化提示：如果不需要保留原数组，可以在输入时直接处理，进一步节省空间。

传球游戏

题目描述

解题思路

这是一个典型的环形 DP 问题。球在同学之间传递，需要记录传递次数和当前持球人编号。

1. 状态表示 使用二维数组 f[i][j]，表示球传递了 i 次之后，最终落在 j 号同学手里的方案数。

2. 状态转移方程 由于同学围成圆圈，需要考虑首尾相接的情况：

   • 1 号同学：只能从 n 号和 2 号传来。 f[i][1] = f[i - 1][n] + f[i - 1][2]
   • 中间同学 j：从 j-1 和 j+1 传来。 f[i][j] = f[i - 1][j - 1] + f[i - 1][j + 1]
   • n 号同学：从 1 号和 n-1 号传来。 f[i][n] = f[i - 1][1] + f[i - 1][n - 1]

3. 初始化 初始时球在 1 号同学手中，传递 0 次。因此 f[0][1] = 1，其余为 0。

4. 填表顺序 先枚举传递次数 i，再枚举同学编号 j。

5. 输出结果 传递 m 次后回到 1 号同学的方案数 f[m][1]。

代码实现

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

乌龟棋

题目描述

解题思路

本题类似于飞行棋，通过消耗不同步数的卡片来前进，目标是获得最大分数。虽然棋盘是一维的，但决策取决于剩余卡片的数量。

1. 状态表示 我们需要知道四种卡片各用了多少张。设 dp[i][j][k][z] 表示使用了 i 张 1 步卡、j 张 2 步卡、k 张 3 步卡、z 张 4 步卡时的最大分数。 当前位置可以通过公式推导：pos = 1 + i*1 + j*2 + k*3 + z*4。

2. 状态转移方程 到达当前状态 dp[i][j][k][z]，最后一步可能是消耗了任意一种卡片。我们需要比较四种来源的最大值：

   • 消耗 1 步卡：来自 dp[i-1][j][k][z]
   • 消耗 2 步卡：来自 dp[i][j-1][k][z]
   • 消耗 3 步卡：来自 dp[i][j][k-1][z]
   • 消耗 4 步卡：来自 dp[i][j][k][z-1]

   取最大值并加上当前格子的分数。

3. 初始化 起点即有分数，dp[0][0][0][0] = a[1]。

4. 填表顺序 四层循环分别枚举四种卡片的数量。

5. 输出结果 所有卡片用完时的最大分数。

代码实现

#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]; // 四维 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;
}

以上便是线性动态规划的四道经典例题。掌握这些基础模型后，面对类似的线性结构问题，关键在于准确定义状态和理清转移关系。