线性动态规划简介
线性 DP 是动态规划问题中最基础、最常见的一类问题。它的特点是状态转移只依赖于前一个或前几个状态,状态之间的关系是线性的,通常可以用一维或者二维数组来存储状态。
台阶问题
题目描述
(题目图片已移除)
题目解析
-
状态表示 dp[i] 表示走到第 i 个台阶的所有方案数。
-
状态转移方程 第 i 个台阶的方案数等于从 i-1 阶到 i-k 阶的所有方案数之和。因为本题数据比较大,用 long long 都无法保证数据不越界,所以题目规定方案数还需要模 100003。第 i 个台阶的方案数等于从 i-1 阶到 i-k 阶的所有方案数之和再模上 100003。注意可能越界访问,比如 i 为 3,k 为 10,i-k 是可能访问到数组负下标的,所以访问台阶时需要保证 i-k 始终大于等于 0。 dp[i] = (dp[i] + dp[i - j]) % 100003(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 位置为结尾的所有子数组中,最大和是多少。
-
状态转移方程 首先明确本题数据是从数组下标 1 开始存储的。如果 n 为 1,也就是只有一个数据,那么最大子段就是它本身,所以 f[i] = a[i]。 如果 n 大于 1,第 i 个格子的最大子段和有两种可能: 第一,最大子段和是它本身 a[i],因为第 i 个格子之前的最大子段和可能是负数。 f[i] = a[i] 第二,最大子段和是第 i 个格子之前的所有子段中的最大子段加上第 i 个格子的数据。 f[i] = f[i - 1] + a[i] 总的来说第 i 个格子的最大子段和就是两种可能中取较大值: f[i] = max(a[i], f[i - 1] + a[i])
-
初始化 当填第一个格子 f[1] 时,根据状态转移方程:f[1] = max(a[1], f[0] + a[1]),而根据我们之前的分析,第一个格子的值就是它本身:f[i] = a[i],所以只要我们把 f[0] 初始化为 0,即可满足要求。
-
填表顺序 从左往右。
-
输出结果 结果为 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;
// 按序填表
for (int i = 1; i <= n; i++) {
f[i] = max(a[i], a[i] + f[i - 1]);
}
// 输出结果
int ret = -0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
ret = max(ret, f[i]);
}
cout << ret << endl;
return 0;
}
// 优化版(无 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;
// 按序填表 + 更新 ret
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;
}
传球游戏
题目描述
(题目图片已移除)
题目解析
-
状态表示 f[i][j] 表示球传递了 i 次之后,最终落在了 j 同学手里一共有多少种方案。
-
状态转移方程 本题推导状态转移方程需要分类讨论,因为题目规定同学围成一个圈,但是我们要用二维线性数组存储数据,所以需要分三种情况: 第一种是接受球的是编号为 1 的同学,此时传递球的同学编号可能是 2 和 n,所以编号为 1 的同学的传球方案数就是 2 和 n 同学的方案数之和: dp[i][1] = dp[i - 1][2] + dp[i - 1][n] 第二种是接受球的是编号为从 2 到 n - 1 的同学,假设为 j,此时传递球的同学编号可能是 j - 1 和 j + 1,所以编号为 1 的同学的传球方案数就是 j - 1 和 j + 1 同学的方案数之和: dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] 第三种是接受球的是编号为 n 的同学,此时传递球的同学编号可能是 1 和 n - 1,所以编号为 n 的同学的传球方案数就是 1 和 n - 1 同学的方案数之和: dp[i][n] = dp[i - 1][1] + dp[i - 1][n - 1]
-
初始化 f[0][1] = 1
-
填表顺序 从上往下依次填每一行。
-
输出结果 f[m][1]
代码
#include <iostream>
using namespace std;
const int N = 40;
int n, m;//n 个同学,传递 m 次
int dp[N][N];//次数,同学编号
int main() {
cin >> n >> m;
// 初始化
dp[0][1] = 1;
// 按序填表
// 从 1 开始枚举传递次数(枚举行)
for (int i = 1; i <= m; i++) {
// 填第 1 个同学
dp[i][1] = dp[i - 1][2] + dp[i - 1][n];
// 填第 2 到 n-1 个同学
// 从 2 开始枚举同学编号(枚举列)
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;
}
乌龟棋
题目描述
(题目图片已移除)
题目解析
-
状态表示 本题 dp 数组每个格子要存储六个信息:走到 x 格子时,用 1 卡片 i 张、用 2 卡片 j 张、用 3 卡片 k 张、用 4 卡片 z 张的情况下的最大分数。所以我们用一个四维 dp 数组存储,需要用到 x 时通过另外 4 个变量计算得到。 x = 1 + i + 2 * j + 3 * k + 4 * z
-
状态转移方程 推导状态转移方程本质就是推导 dp[i][j][k][z],根据我们前面的分析,dp[i][j][k][z] 对应的一维数组下标是 x,那么走到 x 一共有四种可能:分别是从 x-1 到 x、x-2 到 x、x-3 到 x、x-4 到 x。 对于 x-1 来说,它对于的 dp 数组是 dp[i - 1][j][k][z],同理对于 x-2 来说,dp 数组是 dp[i][j - 1][k][z]… 需要处理边界情况,对于变量 i j k z 来说,它们表示抽取各自卡的张数,对 i 来说,取值范围是从 0 到 cnt[1],对于 j 来说,取值范围是从 0 到 cnt[2],k z 同理,所以 i j k z 取值是非负的,所以要访问 dp[i - 1][j][k][z] 时需要保证 i 大于 0,要访问 dp[i][j - 1][k][z] 时需要保证 j 大于 0,k、z 同理。 状态转移方程如下所示,本质我们上面的推导是基于最后一步分析的: dp[i][j][k][z] = max(dp[i - 1][j][k][z], dp[i][j - 1][k][z], dp[i][j][k - 1][z], dp[i][j][k][z - 1]) + a[x]
在代码实现中会用 4 个 for 循环依次枚举 i j k z 的所有取值,枚举一种 i j k z 的取值情况就会将四种可能的状态转移方程作比较,取出最大值作为 dp[i][j][k][z] 的取值。
-
初始化 题目规定乌龟棋子自动获得起点格子的分数,所以 dp[0][0][0][0] = a[1]
-
输出结果 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;//存储棋盘 存储四张卡片各自数目 dp 数组
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 = 0;
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++) {
// x 为当前访问格子下标(数组 a 下标)
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;
}

