线性动态规划是动态规划问题中最基础、最常见的一类。它的特点是状态转移只依赖于前一个或前几个状态，状态之间的关系是线性的，通常可以用一维或者二维数组来存储状态。我们在入门阶段解决的《下楼梯》以及《数字三角形》其实都是线性 DP，一个是一维的，另一个是二维的。下面我们通过四个经典题目来深入理解这一类问题的解法。
台阶问题
本题可以看作是《下楼梯》问题的加强版，总体思路不变。按照动态规划的常规步骤来分析这道题。
状态表示
dp[i] 表示走到第 i 个台阶的所有方案数。
状态转移方程
第 i 个台阶的方案数等于从 i-1 阶到 i-k 阶的所有方案数之和。由于数据较大，结果需要对 100003 取模。需要注意的是，访问台阶时需要保证 i-j 始终大于等于 0，防止负下标越界。
dp[i] = (dp[i] + dp[i - j]) % MOD; // j 从 1 到 k
初始化与填表
直接初始化 dp[0] = 1 即可，然后从 dp[1] 开始往后循环计算。填表顺序从左往右。最终结果即为 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;
}
最大子段和
在处理子序列和子数组问题时，定义状态表示有一个技巧：以某个位置为结尾，结合题意来定义。
状态表示
f[i] 表示以 i 位置为结尾的所有子数组中，最大和是多少。
状态转移方程
根据最后一步划分情况。如果 n 为 1，最大子段就是它本身。如果 n 大于 1，第 i 个格子的最大子段和有两种可能：
- 最大子段和是它本身
a[i]，因为之前的最大子段和可能是负数。 - 最大子段和是第
i个格子之前的所有子段中的最大子段加上第i个格子的数据。 综合起来：
f[i] = max(a[i], f[i - 1] + a[i]);
初始化与结果
将 f[0] 初始化为 0 即可满足要求。填表顺序从左往右。结果为 f 数组中的最大值。为了节省空间，可以在输入时直接更新 f 数组并维护最大值。
#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;
// 按序填表 + 更新 ret
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;
}
传球游戏
题目规定所有同学站成一个圆圈，球可能从左边格子来也可能从右边格子来。需要知道该格子编号和传球次数，因此使用二维数组 f[i][j]。
状态表示
f[i][j] 表示球传递了 i 次之后，最终落在了 j 号同学手里一共有多少种方案。
状态转移方程
由于是环形结构，需要分三种情况讨论：
- 接受球的是编号为 1 的同学，来源可能是 2 和
n。dp[i][1] = dp[i - 1][2] + dp[i - 1][n] - 接受球的是编号为 2 到
n-1的同学j，来源可能是j-1和j+1。dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] - 接受球的是编号为
n的同学，来源可能是 1 和n-1。dp[i][n] = dp[i - 1][1] + dp[i - 1][n - 1]
初始化与填表
第一行表示传球次数为 0，此时球在一号同学手里，所以 dp[0][1] = 1。填表顺序从上往下依次填每一行。最终结果是 dp[m][1]。
#include <iostream>
using namespace std;
const int N = 40;
int n, m;
int dp[N][N];
int main() {
cin >> n >> m;
// 初始化
dp[0][1] = 1;
// 按序填表
for (int i = 1; i <= m; i++) {
// 填第 1 个同学
dp[i][1] = dp[i - 1][2] + dp[i - 1][n];
// 填第 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][1] + dp[i - 1][n - 1];
}
cout << dp[m][1] << endl;
return 0;
}
乌龟棋
本题类似飞行棋，抽卡片决定走多少步，目标是找出从起点走到终点格子的最大分数。
状态表示
需要记录走到某格子时，用 1 卡片 i 张、2 卡片 j 张、3 卡片 k 张、4 卡片 z 张的情况下的最大分数。虽然本质涉及五维信息，但一维数组下标 x 可以通过另外 4 个变量计算出来：x = 1 + i + 2*j + 3*k + 4*z。因此使用四维 dp 数组存储。
状态转移方程
走到 x 一共有四种可能：分别是从 x-1 到 x、x-2 到 x、x-3 到 x、x-4 到 x。对应消耗不同种类的卡片。
例如从 x-1 过来，消耗一张 1 卡片，状态为 dp[i-1][j][k][z]。
注意边界条件，访问 dp[i-1] 时需保证 i > 0。
t = max(t, dp[i - 1][j][k][z] + a[x]);
同理处理其他三种卡片。
初始化与填表
题目规定乌龟棋子自动获得起点格子的分数，所以 dp[0][0][0][0] = a[1]。
代码实现中用 4 个 for 循环依次枚举 i, j, k, z 的所有取值，取出最大值作为当前状态的取值。最终结果是 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;
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;
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 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;
}
