线性动态规划基础详解：4 道经典例题与优化技巧

前言

动态规划（DP）是算法学习中的核心难点，也是竞赛和面试的必考点。线性 DP 作为最基础的分支，状态转移具有明显的线性关系，逻辑清晰，非常适合作为入门切入点。

本文带大家吃透基础线性 DP，从核心思想拆解到 4 道经典例题，再到空间优化技巧。

一、线性 DP 核心思想：把复杂问题'线性化'

1.1 线性 DP 的定义

线性 DP 是动态规划的一种特殊形式，其核心特点是状态之间的转移关系呈线性结构。简单来说，DP 状态可以用一维或二维数组表示，推导顺序是线性的——要么从左到右、要么从上到下。

例如一维线性 DP 中，dp[i] 的取值只依赖 dp[i-1]、dp[i-2] 等前面的状态；二维线性 DP 中，dp[i][j] 也只依赖相邻的线性状态。

1.2 线性 DP 解题四步走

解决任何线性 DP 问题，都可以遵循这四个核心步骤：

1. 状态表示：定义 DP 数组的含义。
2. 状态转移方程：推导当前状态如何由前面的状态计算得出。
3. 初始化：确定 DP 数组的初始值。
4. 填表顺序：根据状态转移方程，确定 DP 数组的计算顺序。

1.3 线性 DP 的优势

相比于其他 DP 分支，线性 DP 的优势在于逻辑清晰、代码简洁、实用性强，很多实际问题（如路径计数、最值问题）都可以抽象为线性 DP 模型。

二、经典例题实战：从易到难吃透基础线性 DP

例题 1：台阶问题（洛谷 P1192）—— 一维线性 DP 入门

题目描述

有 N 级台阶，一开始在底部，每次可以向上迈 1~K 级台阶，问到达第 N 级台阶有多少种不同方式？结果对 100003 取模。 输入：两个正整数 N, K（1≤N≤1e5，1≤K≤100） 输出：到达第 N 级台阶的不同方式数（mod 100003）

思路拆解

1. 状态表示：定义 dp[i] 表示'到达第 i 级台阶的不同方式数'。
2. 状态转移方程：要到达第 i 级，最后一步可以从 i-1 到 i-K 级迈过来。dp[i] = (dp[i-1] + dp[i-2] + ... + dp[i-K]) % MOD
3. 初始化：dp[0] = 1。
4. 填表顺序：从左到右依次计算 dp[1] 到 dp[N]。

代码实现（基础版）

#include <iostream>
using namespace std;
const int N = 1e5 + 10, MOD = 1e5 + 3;
int n, k;
int dp[N];
int main() {
    cin >> n >> k;
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k && i - j >= 0; j++) {
            dp[i] = (dp[i] + dp[i - j]) % MOD;
        }
    }
    cout << dp[n] << endl;
    return 0;
}

时间复杂度分析

基础版的时间复杂度是 O(N*K)。当 N=1e5、K=100 时，总运算量是 1e7，可以通过。但如果 K 更大，会超时。

优化技巧：前缀和优化（O(N) 复杂度）

观察状态转移方程，dp[i] 是前 K 个状态的和。我们可以用一个前缀和数组 sum[i] 表示 dp[0]~dp[i] 的和，将求和转化为 O(1)。

#include <iostream>
using namespace std;
const int N = 1e5 + 10, MOD = 1e5 + 3;
int n, k;
int dp[N], sum[N];
int main() {
    cin >> n >> k;
    dp[0] = 1;
    sum[0] = dp[0];
    for (int i = 1; i <= n; i++) {
        if (i - k > 0) {
            dp[i] = (sum[i-1] - sum[i - k - 1] + MOD) % MOD;
        } else {
            dp[i] = sum[i-1] % MOD;
        }
        sum[i] = (sum[i-1] + dp[i]) % MOD;
    }
    cout << dp[n] << endl;
    return 0;
}

例题 2：最大子段和（洛谷 P1115）—— 一维线性 DP 的最值问题

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段，使得这段的和最大。 输入：第一行是序列长度 n；第二行是 n 个整数（-1e4 ≤ a[i] ≤ 1e4，1≤n≤2e5） 输出：最大子段和

思路拆解

1. 状态表示：dp[i] 表示'以第 i 个元素为结尾的所有连续子段的最大和'。
2. 状态转移方程：dp[i] = max(a[i], dp[i-1] + a[i])
3. 初始化：dp[1] = a[1]。
4. 填表顺序：从左到右依次计算，最终答案是 dp 数组中的最大值。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N], dp[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dp[1] = a[1];
    int max_sum = dp[1];
    for (int i = 2; i <= n; i++) {
        dp[i] = max(a[i], dp[i-1] + a[i]);
        max_sum = max(max_sum, dp[i]);
    }
    cout << max_sum << endl;
    return 0;
}

空间优化：O(1) 空间

观察发现，dp[i] 只依赖 dp[i-1]，因此不需要用数组存储整个 dp 序列，只用一个变量记录前一个状态即可。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N];
int main() {
    cin >> n;
    int prev = 0, max_sum = -1e9;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prev = max(a[i], prev + a[i]);
        max_sum = max(max_sum, prev);
    }
    cout << max_sum << endl;
    return 0;
}

例题 3：传球游戏（洛谷 P1057）—— 二维线性 DP 的状态设计

题目描述

n 个同学站成一个圆圈，小蛮（1 号同学）手里拿着球，传了 m 次后，球回到小蛮手里的不同传球方法有多少种？ 输入：两个整数 n, m（3≤n≤30，1≤m≤30） 输出：符合条件的传球方法数

思路拆解

1. 状态表示：dp[i][j] 表示'传球 i 次后，球在第 j 号同学手里的方法数'。
2. 状态转移方程：
   • 中间同学：dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
   • 1 号同学：dp[i][1] = dp[i-1][n] + dp[i-1][2]
   • n 号同学：dp[i][n] = dp[i-1][n-1] + dp[i-1][1]
3. 初始化：dp[0][1] = 1。
4. 填表顺序：先枚举传球次数 i，再枚举同学编号 j。

代码实现

#include <iostream>
using namespace std;
const int N = 50;
int n, m;
int dp[N][N];
int main() {
    cin >> n >> m;
    dp[0][1] = 1;
    for (int i = 1; i <= m; i++) {
        dp[i][1] = dp[i-1][n] + dp[i-1][2];
        for (int j = 2; j < n; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
        }
        dp[i][n] = dp[i-1][n-1] + dp[i-1][1];
    }
    cout << dp[m][1] << endl;
    return 0;
}

例题 4：乌龟棋（洛谷 P1541）—— 多维线性 DP 的状态优化

题目描述

乌龟棋的棋盘有 N 个格子，每个格子有分数。玩家有 M 张爬行卡片，分为 4 种类型（1、2、3、4），每张卡片只能用一次。乌龟从第 1 格出发，用完全部卡片到达第 N 格，求最大得分。 输入：

• 第一行：N, M（1≤N≤350，1≤M≤120）
• 第二行：N 个整数，第 i 个是第 i 格的分数
• 第三行：M 个整数，每张卡片的类型 输出：最大得分

思路拆解

1. 状态表示：dp[a][b][c][d] 表示'使用 a 张 1 型、b 张 2 型、c 张 3 型、d 张 4 型卡片时的最大得分'，对应位置 pos = 1 + a + 2b + 3c + 4d。
2. 状态转移方程：dp[a][b][c][d] = max(四种前序状态) + score[pos]
3. 初始化：dp[0][0][0][0] = score[1]。
4. 填表顺序：从小到大枚举四种卡片的使用次数。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 360, M = 50;
int n, m;
int score[N];
int cnt[5];
int dp[M][M][M][M];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        cnt[t]++;
    }
    dp[0][0][0][0] = score[1];
    for (int a = 0; a <= cnt[1]; a++) {
        for (int b = 0; b <= cnt[2]; b++) {
            for (int c = 0; c <= cnt[3]; c++) {
                for (int d = 0; d <= cnt[4]; d++) {
                    int pos = 1 + a + 2*b + 3*c + 4*d;
                    int& curr = dp[a][b][c][d];
                     (a > ) curr = (curr, dp[a][b][c][d] + score[pos]);
                     (b > ) curr = (curr, dp[a][b][c][d] + score[pos]);
                     (c > ) curr = (curr, dp[a][b][c][d] + score[pos]);
                     (d > ) curr = (curr, dp[a][b][c][d] + score[pos]);
                }
            }
        }
    }
    cout << dp[cnt[]][cnt[]][cnt[]][cnt[]] << endl;
     ;
}

复杂度分析

四种卡片的最大数量都是 40，四维循环总次数是 40^4 = 2,560,000，完全可以通过。

三、线性 DP 常见优化技巧总结

1. 空间优化：滚动数组 / 变量。如果当前状态只依赖前几个状态，只用存储必要的前序状态。
2. 时间优化：前缀和 / 后缀和。当状态转移需要求和，用前缀和数组预处理，将 O(K) 转化为 O(1)。
3. 状态维度优化：通过数学关系减少 DP 数组的维度。
4. 边界处理优化：合理设置边界值，避免越界或逻辑错误。

四、线性 DP 实战练习建议

1. 基础巩固：洛谷 P10250 下楼梯、P1115 最大子段和、P1057 传球游戏。
2. 进阶练习：洛谷 P1541 乌龟棋、P1216 数字三角形。
3. 总结归纳：思考状态定义、转移方程推导及优化空间。

总结

线性 DP 是后续学习背包 DP、区间 DP 等复杂 DP 的基础。打好这个基础，后面的学习会事半功倍。祝大家都能攻克 DP 这个难点，在算法路上越走越远！