【算法基础篇】（二十八）线性动态规划之基础 DP 超详解：从入门到实战，覆盖 4 道经典例题 + 优化技巧
目录
例题 1：台阶问题（洛谷 P1192）—— 一维线性 DP 入门
例题 2：最大子段和（洛谷 P1115）—— 一维线性 DP 的最值问题
例题 3：传球游戏（洛谷 P1057）—— 二维线性 DP 的状态设计
例题 4：乌龟棋（洛谷 P1541）—— 多维线性 DP 的状态优化
前言
动态规划（DP）绝对是算法学习路上的 “拦路虎”—— 入门晦涩、题型繁多、题目难度跨度大，不少同学刚接触就被绕晕。但它又是竞赛和面试中的 “必考点”，想拿高分根本绕不开。
而线性 DP 作为动态规划中最基础、最核心的分支，就像是 DP 世界的 “入门钥匙”。它的状态转移具有明显的线性关系，要么依赖前一个状态，要么依赖前几个状态，逻辑相对清晰，非常适合作为 DP 的入门切入点。
今天这篇文章，就带大家吃透基础线性 DP—— 从核心思想拆解到 4 道经典例题（，再到空间优化技巧，每一步都讲得明明白白。不管你是刚接触 DP 的新手，还是想巩固基础的老手，都能有所收获！
一、线性 DP 核心思想：把复杂问题 “线性化”
在正式讲例题之前，我们先搞懂：什么是线性 DP？它的核心逻辑是什么？
1.1 线性 DP 的定义
线性 DP 是动态规划的一种特殊形式，其核心特点是状态之间的转移关系呈线性结构。简单来说，我们定义的 DP 状态可以用一维或二维数组表示，并且状态的推导顺序是 “线性的”—— 要么从左到右、要么从上到下，不会出现复杂的跳转。
比如一维线性 DP 中，dp[i]的取值只依赖dp[i-1]、dp[i-2]等前面的状态；二维线性 DP 中，dp[i][j]也只依赖dp[i-1][j]、dp[i][j-1]等相邻的线性状态。
1.2 线性 DP 解题四步走
解决任何线性 DP 问题，都可以遵循这四个核心步骤，堪称 “万能模板”：
状态表示：定义 DP 数组的含义（这是 DP 的灵魂，也是最关键的一步）；状态转移方程：推导当前状态如何由前面的状态计算得出；初始化：确定 DP 数组的初始值（避免后续计算出现逻辑错误）；填表顺序：根据状态转移方程，确定 DP 数组的计算顺序（保证计算当前状态时，依赖的状态已经计算完成）。
这四步看似简单，但实际应用中需要灵活调整。后面的例题会反复用到这个框架，大家可以慢慢体会。
1.3 线性 DP 的优势
相比于其他 DP 分支（如区间 DP、背包 DP），线性 DP 的优势在于：
逻辑清晰：状态转移关系简单，容易理解和推导；代码简洁：不需要复杂的状态枚举，实现难度低；实用性强：很多实际问题（如路径计数、最值问题）都可以抽象为线性 DP 模型。
二、经典例题实战：从易到难吃透基础线性 DP
下面我们通过 4 道经典例题，一步步应用 “解题四步走”，手把手教大家如何解决线性 DP 问题。每道题都会详细拆解思路，附上完整代码和优化技巧。
例题 1：台阶问题（洛谷 P1192）—— 一维线性 DP 入门
题目链接：https://www.luogu.com.cn/problem/P1192
题目描述
有 N 级台阶，你一开始在底部，每次可以向上迈 1~K 级台阶，问到达第 N 级台阶有多少种不同方式？结果对 100003 取模。
输入：两个正整数 N, K（1≤N≤1e5，1≤K≤100）
输出：到达第 N 级台阶的不同方式数（mod 100003）
思路拆解
1. 状态表示
我们定义dp[i]表示 “到达第 i 级台阶的不同方式数”。目标就是计算dp[N]。
2. 状态转移方程
要到达第 i 级台阶，最后一步可以是从第i-1级迈 1 步、从i-2级迈 2 步、……、从i-K级迈 K 步（前提是i-j ≥ 0）。
因此，到达第 i 级的方式数，就是所有合法前序台阶的方式数之和：dp[i] = (dp[i-1] + dp[i-2] + ... + dp[i-K]) % MOD
3. 初始化
dp[0] = 1：表示在第 0 级台阶（底部），有一种 “不动” 的方式（作为所有台阶的起始状态）。
4. 填表顺序
从左到右依次计算dp[1]到dp[N]，因为dp[i]依赖前面的dp[i-1]到dp[i-K]。
代码实现（基础版）
#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 更大（比如 K=1e5），这个复杂度就会达到 O (N²)，会超时。
优化技巧：前缀和优化（O (N) 复杂度）
观察状态转移方程，dp[i]是前 K 个状态的和。我们可以用一个前缀和数组sum[i]表示dp[0]~dp[i]的和，这样：dp[i] = (sum[i-1] - (i-K-1 >= 0 ? sum[i-K-1] : 0)) % MOD
优化后的代码：
#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]; // sum[i] = dp[0] + dp[1] + ... + dp[i] for (int i = 1; i <= n; i++) { // 计算dp[i] = sum[i-1] - sum[i-K-1]（如果i-K-1 >=0） 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; } 优化后时间复杂度降至 O (N)，即使 N=1e6 也能轻松通过。
例题 2：最大子段和（洛谷 P1115）—— 一维线性 DP 的最值问题
题目链接：https://www.luogu.com.cn/problem/P1115
题目描述
给出一个长度为 n 的序列 a，选出其中连续且非空的一段，使得这段的和最大。
输入：第一行是序列长度 n；第二行是 n 个整数（-1e4 ≤ a [i] ≤ 1e4，1≤n≤2e5）
输出：最大子段和
思路拆解
这道题是经典的 “最大子段和” 问题，也是线性 DP 的经典应用。很多同学可能会想到暴力枚举所有子段，但 O (n²) 的复杂度在 n=2e5 时会直接超时，而 DP 可以做到 O (n)。
1. 状态表示
关键是如何定义 DP 状态。如果定义dp[i]为 “前 i 个元素的最大子段和”，会很难推导转移方程。
正确的状态表示：dp[i]表示 “以第 i 个元素为结尾的所有连续子段的最大和”。
为什么这样定义？因为连续子段的特性是 “结尾固定”，这样可以自然地利用前一个状态推导当前状态。
2. 状态转移方程
以第 i 个元素为结尾的子段，有两种情况：
子段只包含第 i 个元素：此时和为a[i]；子段包含第 i 个元素和前面的部分：此时和为dp[i-1] + a[i]（因为dp[i-1]是以前 i-1 个元素为结尾的最大子段和，加上 a [i] 就形成了以 i 为结尾的更长子段）。
因此，状态转移方程为：dp[i] = max(a[i], dp[i-1] + a[i])
3. 初始化
dp[1] = a[1]（以第一个元素为结尾的子段，最大和就是它本身）。
4. 填表顺序
从左到右依次计算dp[1]到dp[n]，最终答案是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; // prev记录dp[i-1] for (int i = 1; i <= n; i++) { cin >> a[i]; prev = max(a[i], prev + a[i]); // 直接更新prev max_sum = max(max_sum, prev); } cout << max_sum << endl; return 0; } 优化后空间复杂度从 O (n) 降至 O (1)，对于大数据量非常友好。
例题 3：传球游戏（洛谷 P1057）—— 二维线性 DP 的状态设计
题目描述
n 个同学站成一个圆圈，小蛮（1 号同学）手里拿着球，传了 m 次后，球回到小蛮手里的不同传球方法有多少种？
输入：两个整数 n, m（3≤n≤30，1≤m≤30）
输出：符合条件的传球方法数
思路拆解
这道题的状态需要考虑两个维度：传球次数和当前持球的同学编号，因此是二维线性 DP。
1. 状态表示
定义dp[i][j]表示 “传球 i 次后，球在第 j 号同学手里的方法数”。目标是计算dp[m][1]。
2. 状态转移方程
因为同学站成圆圈，所以持球同学的左右邻居需要特殊处理：
对于中间同学（2≤j≤n-1）：球可以从 j-1 号或 j+1 号传来，因此dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]；对于 1 号同学（小蛮）：球可以从 n 号（圆圈左边）或 2 号（右边）传来，因此dp[i][1] = dp[i-1][n] + dp[i-1][2]；对于 n 号同学：球可以从 n-1 号（左边）或 1 号（右边）传来，因此dp[i][n] = dp[i-1][n-1] + dp[i-1][1]。
3. 初始化
dp[0][1] = 1：传球 0 次（球没传出去），球在 1 号同学手里，只有 1 种方法。
4. 填表顺序
先枚举传球次数 i（从 1 到 m），再枚举同学编号 j（从 1 到 n）。因为dp[i][j]依赖dp[i-1][...]，必须先计算完 i-1 次传球的所有状态，再计算 i 次。
代码实现
#include <iostream> using namespace std; const int N = 50; int n, m; int dp[N][N]; // dp[i][j]：传i次球后在j号手里的方法数 int main() { cin >> n >> m; dp[0][1] = 1; // 初始化：0次传球在1号手里 for (int i = 1; i <= m; i++) { // 处理1号同学 dp[i][1] = dp[i-1][n] + dp[i-1][2]; // 处理中间同学（2~n-1） 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][n-1] + dp[i-1][1]; } cout << dp[m][1] << endl; return 0; } 代码验证
以示例输入3 3为例：
传 1 次：球在 2 或 3 号手里，dp[1][2]=1，dp[1][3]=1；传 2 次：球在 1 或 3 号（从 2 号传来）、1 或 2 号（从 3 号传来），dp[2][1]=2，dp[2][2]=1，dp[2][3]=1；传 3 次：球在 2 或 3 号（从 1 号传来）、1 或 3 号（从 2 号传来）、1 或 2 号（从 3 号传来），dp[3][1]=2，与示例输出一致。
例题 4：乌龟棋（洛谷 P1541）—— 多维线性 DP 的状态优化
题目链接：https://www.luogu.com.cn/problem/P1541
题目描述
乌龟棋的棋盘有 N 个格子，每个格子有分数。玩家有 M 张爬行卡片，分为 4 种类型（1、2、3、4），每张卡片只能用一次。乌龟从第 1 格出发，用完全部卡片到达第 N 格，求最大得分。
输入：
- 第一行：N, M（1≤N≤350，1≤M≤120）
- 第二行：N 个整数，第 i 个是第 i 格的分数
- 第三行：M 个整数，每张卡片的类型
输出：最大得分
思路拆解
这道题的状态需要考虑 4 种卡片的使用次数，因此是四维线性 DP，但可以通过数学关系优化维度。
1. 状态表示（优化前）
最初的想法是定义dp[a][b][c][d]表示 “使用 a 张 1 型卡片、b 张 2 型卡片、c 张 3 型卡片、d 张 4 型卡片时的最大得分”。
但这样会有一个问题：使用的卡片总数是a+b+c+d，对应的位置是1 + 1*a + 2*b + 3*c + 4*d（因为从第 1 格出发，每张卡片对应前进的步数）。因此，位置可以通过 a、b、c、d 计算得出，不需要额外存储位置维度。
优化后的状态表示：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]可以由四种前序状态转移而来（取决于最后使用的是哪种卡片）：
最后使用 1 型卡片（a≥1）：dp[a-1][b][c][d] + score[pos]；最后使用 2 型卡片（b≥1）：dp[a][b-1][c][d] + score[pos]；最后使用 3 型卡片（c≥1）：dp[a][b][c-1][d] + score[pos]；最后使用 4 型卡片（d≥1）：dp[a][b][c][d-1] + score[pos]。
因此，状态转移方程为：dp[a][b][c][d] = max(四种前序状态) + score[pos]
3. 初始化
dp[0][0][0][0] = score[1]：使用 0 张卡片时，乌龟在第 1 格，得分是第 1 格的分数。
4. 填表顺序
枚举四种卡片的使用次数 a、b、c、d（从 0 到各自的最大数量），因为dp[a][b][c][d]依赖的是使用次数更少的状态，所以顺序是从小到大枚举。
代码实现
#include <iostream> #include <algorithm> using namespace std; const int N = 360, M = 50; int n, m; int score[N]; // 每个格子的分数 int cnt[5]; // 四种卡片的数量（cnt[1]是1型卡片数量） int dp[M][M][M][M]; // 四维DP数组 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]++; // 统计每种卡片的数量 } // 初始化：0张卡片时在第1格 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]; // 从使用1型卡片的状态转移 if (a > 0) { curr = max(curr, dp[a-1][b][c][d] + score[pos]); } // 从使用2型卡片的状态转移 if (b > 0) { curr = max(curr, dp[a][b-1][c][d] + score[pos]); } // 从使用3型卡片的状态转移 if (c > 0) { curr = max(curr, dp[a][b][c-1][d] + score[pos]); } // 从使用4型卡片的状态转移 if (d > 0) { curr = max(curr, dp[a][b][c][d-1] + score[pos]); } } } } } // 最终状态：使用完所有卡片 cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl; return 0; } 复杂度分析
四种卡片的最大数量都是 40（题目规定每种卡片不超过 40 张），因此四维循环的总次数是 40^4 = 2,560,000，完全可以通过。
这道题的核心是 “状态维度优化”—— 通过位置与卡片使用次数的数学关系，减少了一维状态，让代码更容易实现。
三、线性 DP 常见优化技巧总结
在前面的例题中，我们用到了多种优化技巧，这里集中总结，方便大家记忆和应用：
1. 空间优化：滚动数组 / 变量
核心思想：如果当前状态只依赖前几个状态，不需要存储整个 DP 数组，只用存储必要的前序状态。
一维 DP 优化：如最大子段和，用一个变量记录dp[i-1]，替代整个dp数组；二维 DP 优化：如后面的路径 DP，可以用一维数组 “滚动” 更新，减少空间复杂度。
2. 时间优化：前缀和 / 后缀和
核心思想：当状态转移需要求和（如台阶问题中dp[i]是前 K 个状态的和），用前缀和数组预处理，将 O (K) 的求和转化为 O (1)。
3. 状态维度优化
核心思想：通过数学关系或逻辑推导，减少 DP 数组的维度（如乌龟棋，用卡片使用次数推导位置，减少了 “位置” 这一维）。
4. 边界处理优化
核心思想：初始化时合理设置边界值，避免后续计算出现越界或逻辑错误。
最值问题：如果求最大值，将无效状态初始化为-∞；如果求最小值，初始化为+∞；计数问题：将基础状态初始化为 1（如传球游戏的dp[0][1] = 1），其他状态初始化为 0。
四、线性 DP 实战练习建议
掌握了上面的例题和技巧后，建议大家通过以下步骤巩固学习：
1. 基础巩固（必做）
- 洛谷 P10250 下楼梯（简化版台阶问题，K=3）；
- 洛谷 P1115 最大子段和（二刷优化版）；
- 洛谷 P1057 传球游戏（尝试自己推导状态转移）。
2. 进阶练习（提升）
- 洛谷 P1541 乌龟棋（重点练习多维 DP 的状态设计）；
- 洛谷 P1216 数字三角形（二维线性 DP，路径最值问题）。
3. 总结归纳
每做完一道题，建议大家都要思考一下：
状态是如何定义的？为什么这样定义？状态转移方程是如何推导的？有没有优化空间？可以从哪些角度优化？
总结
线性 DP 是后续学习背包 DP、区间 DP 等复杂 DP 的基础，打好这个基础，后面的学习会事半功倍。如果遇到问题，不妨回头再看看这篇文章，重温解题四步走和优化技巧。
最后，祝大家都能攻克 DP 这个 “拦路虎”，在算法路上越走越远！
