知识总结
矩阵DP，即题目给出的数据模型是一个二维矩阵（比如题目中出现“棋盘”、“网格”…），求解时需要在矩阵中进行操作。
矩阵DP 实际上是 线性DP 的维度升级，与 线性DP 求解思路类似，不过由于多出了维度，其包含的内容也更丰富，设计状态时根据情境增加维度到二维三维甚至四维。
经典例题
[USACO1.5] [IOI1994]数字三角形 Number Triangles
思路
- 本题是一道简单的二维DP，找到 a[i][j] 最优解的来源，应该是来自存储矩阵的左上方 a[i-1][j-1] 和右上方 a[i-1][j]，由此易推出状态转移方程：a[i][j] = a[i][j] + max(a[i-1][j-1], a[i-1][j])。
- 更新 a[i][j] 过程中同步打擂台求最值，最后所得 maxs 即为结果。
代码
#include <bits/stdc++.h>
using namespace std;
int r, a[1005][1005], maxs;
int main(){
cin >> r;
for(int i = 1; i <= r; i++){
for(int j = 1; j <= i; j++){
cin >> a[i][j];
a[i][j] = a[i][j] + max(a[i-1][j-1], a[i-1][j]);
maxs = max(maxs, a[i][j]);
}
}
cout << maxs;
return 0;
}
[NOIP2002 普及组] 过河卒
思路
- 本题是一道经典的基础二维DP问题。对于点 a[i][j] 来说，其状态转移方程就是 a[i-1][j] 与 a[i][j-1] 的路径数总和（前提是该点可达）。
- 需要特别注意以下几点：
- 答案数据增长会很快，需要 long long 数组存答案；
- 在标记马的控制点和判断上一步的点是否可达时，推算的坐标出现减法计算都要特判下是否越界，只有 >= 0 的坐标才是合法的；
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
/* In: 20 20 4 0 Out: 56477364570 */
int bx, by, hx, hy;
ll a[25][25]; // a[i][j]：从 A(0, 0) 到 (i, j) 的路径数
int main(){
cin >> bx >> by >> hx >> hy;
// 把马的坐标及其控制点标记为不可走 (-1)
a[hx][hy] = -1;
int d[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
{1, -2}, {1, 2}, {2, -1}, {2, 1}};
for(int i = 0; i < 8; i++){
int x = hx + d[i][0], y = hy + d[i][1];
if(x >= 0 && y >= 0){ // 避免下标越界
a[x][y] = -1;
}
}
a[0][0] = 1; // 初始化起点路径数为 1 表示可由此出发
for(int i = 0; i <= bx; i++){
for(int j = 0; j <= by; j++){
if(a[i][j] != -1){ // 若该处可达
a[i][j] += (a[i-1][j] != -1 && i >= 1 ? a[i-1][j] : 0);
a[i][j] += (a[i][j-1] != -1 && j >= 1 ? a[i][j-1] : 0);
}
}
}
cout << a[bx][by];
return 0;
}
[SHOI2002] 滑雪
思路
- 本题可以采用记忆化搜索的方式进行动态规划。
- 记忆化搜索：通过递归结构由后向前地求解子问题，转移方式与动态规划类似，本题定义 s(x, y) 求解 (x, y) 为起点的最大滑坡长度。
- 状态定义： f[x][y] 记录由 (x, y) 出发能得到的最长滑坡长度。
- 状态转移： 题目规定只能从高处滑到低处，因此对于 (x, y) 来说，它能获得的最大滑坡长度取决于它的相邻点 (x1, y1) 中比它低的点能获得的最大滑坡长度，在此基础上加 1 即为 (x, y) 的解。转移方程为：f[x][y] = max(f[x][y], s(x1, y1) + 1)。
代码
#include <bits/stdc++.h>
using namespace std;
int r, c, maxl, a[105][105], f[105][105];
int d[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int s(int x, int y){
if(f[x][y]) return f[x][y]; // 记忆化搜索
f[x][y] = 1; // 每个点的最小长度为 1
for(int i = 0; i < 4; i++){
int x1 = x + d[i][0], y1 = y + d[i][1];
if(x1 >= 1 && x1 <= r && y1 >= 1 && y1 <= c
&& (a[x1][y1] < a[x][y])){ // (x, y) -> (x1, y1)
f[x][y] = max(f[x][y], s(x1, y1) + 1);
}
}
return f[x][y];
}
int main(){
cin >> r >> c;
for(int i = 1; i <= r; i++){
for(int j = 1; j <= c; j++){
cin >> a[i][j];
}
}
for(int i = 1; i <= r; i++){
for(int j = 1; j <= c; j++){
maxl = max(maxl, s(i, j));
}
}
cout << maxl;
return 0;
}
三倍经验
思路
- 这道题在原始的数字三角形基础上，新增了一个条件：可以选择金字塔中的不多于 k 个数字让他们成为原来的 3 倍，因此需要新加一个维度记录当前使用 * 3 的次数，范围 0 ~ k。
- 状态定义：f[i][j][t]: 从 (i, j) 出发恰用 t 次乘 3 的最大值。
- 边界初始化：f[1][1][0] = a[1][1]（起点时不用 * 3），f[1][1][1] = 3 * a[1][1] （起点时用 1 次 * 3）。
- 状态转移：分两种情况讨论：当前元素 * 3 和 当前元素不 * 3。
- 当前元素不 * 3，直接从左上或右上状态转移来：f[i][j][t] = a[i][j]+max(f[i-1][j-1][t], f[i-1][j][t])
- 当前元素可 * 3，则在选择当前 * 3 与之前算出的当前元素不 * 3 中取最大（上一步用了 t-1 次 * 3）：f[i][j][t] = max(3 * a[i][j] + max(f[i-1][j-1][t-1], f[i-1][j][t-1])， f[i][j][t])
- 注意：
- 本题数据比较大，数组要用 long long 存；
- 因为题目中 a[i][j] 可以是负数，f[][][] 数组要初始化为很小的数才能保证比较的正确性。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, k;
ll maxs = LONG_LONG_MIN, a[105][105], f[105][105][105 * 105 / 2];
int main(){
cin >> n >> k; // f[i][j][t]: 从 (i, j) 出发恰用 t 次乘 3 的最大值
memset(f, 0x8f, sizeof(f)); // 初始化 f[i][j][t] 为极小值
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
cin >> a[i][j];
}
}
f[1][1][0] = a[1][1], f[1][1][1] = 3 * a[1][1];
for(int i = 2; i <= n; i++){ // 从上往下推
for(int j = 1; j <= i; j++){
for(int t = 0; t <= k; t++){
// 状态转移情况 1：当前不 * 3，直接从左上或右上状态转移来
f[i][j][t] = a[i][j]+max(f[i-1][j-1][t], f[i-1][j][t]);
// 状态转移情况 2：当前 可 * 3，上一步用了 t-1 次 * 3
if(t >= 1) // 在选择当前 * 3 与当前 不 * 3 中取最大
f[i][j][t] = max(f[i][j][t], 3 * a[i][j]
+ max(f[i-1][j-1][t-1], f[i-1][j][t-1]));
}
}
}
for(int j = 1; j <= n; j++){
for(int t = 0; t <= k; t++){
maxs = max(maxs, f[n][j][t]);
}
}
cout << maxs;
return 0;
}
[CSP-J2020] 方格取数
思路
- 本题可以向上，向下和向右走，并且不能重复经过已经走过的方格，因此向下和向上是不可能先后出现的，用一个二维 dp 同时推三个方向就会有问题。
- 对于每个点接下来朝三个可选方向的走法，是依其上一步走的方向而定的（比如上一步是向下走的，该处点就不能向上走了，不然又会回到上一步的点）。我们可以用三个二维数组分别记录 (i, j) 选择不同方向的结果。
- 由于横向只能往右走，因此可以从左往右推每一列，对每列再分别讨论该点朝上和朝下的情况。
- 状态定义：
- d[i][j]：从上往向下走到达 (i, j) 的取数之和最大值；
- r[i][j]：从左往右走到达 (i, j) 的取数之和最大值；
- u[i][j]：从下往上走到达 (i, j) 的取数之和最大值；
- 边界初始化：
- 对起点来说，不存在上一步，该点结果三个方向都为 a[1][1]：d[1][1] = u[1][1] = r[1][1] = a[1][1];
- 对第一列元素来说，只能从上往下走得到，可以用前缀和求： d[i][1] = d[i – 1][1] + a[i][1]。
- 状态转移：分三种情况讨论：→，↓，↑。
- 推 →： 上一步可以是 ↑ 或 ↓ 或 →：r[i][j]=a[i][j]+max(max(u[i][j-1], d[i][j-1]), r[i][j-1])
- 推 ↓： 上一步只能是 ↓ 或 →：d[i][j] = a[i][j] + max(r[i – 1][j], d[i – 1][j])
- 推 ↑： 上一步只能是 ↑ 或 →：u[i][j] = a[i][j] + max(u[i + 1][j], r[i + 1][j])
- 注意：
- 本题数据比较大，数组要用 long long 存；
- 因为题目中 a[i][j] 可以是负数，三个方向数组都要初始化为很小的数才能保证比较的正确性。
代码
#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
typedef long long ll;
int n, m, a[maxn][maxn];
ll d[maxn][maxn], u[maxn][maxn], r[maxn][maxn];
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &a[i][j]);
d[i][j] = u[i][j] = r[i][j] = LONG_LONG_MIN;
}
if(i == 1) // 对起点来说，不存在上一步，该点结果三个方向都为 a[1][1]
d[1][1] = u[1][1] = r[1][1] = a[1][1];
else // i: 2 ~ n, ↓ 推 d[i][1] 初始化第一列值
d[i][1] = d[i - 1][1] + a[i][1];
}
for(int j = 2; j <= m; j++){ // 从第一列开始推 2 ~ m 列
for(int i = 1; i <= n; i++) // 推 →： 上一步可以是 ↑ 或 ↓ 或 →
r[i][j]=a[i][j]+max(max(u[i][j-1], d[i][j-1]), r[i][j-1]);
for(int i = 2; i <= n; i++) // 推 ↓： 上一步只能是 ↓ 或 →
d[i][j] = a[i][j] + max(r[i - 1][j], d[i - 1][j]);
for(int i = n - 1; i >= 1; i--) // 推 ↑： 上一步只能是 ↑ 或 →
u[i][j] = a[i][j] + max(u[i + 1][j], r[i + 1][j]);
}
printf("%lld", max(d[n][m], r[n][m])); // 最后一步只可能是向下或者向右走到的
return 0;
}
[NOIP2000 提高组] 方格取数
思路
- 本题如果用贪心分两次 DP，得到的结果不一定就是最优的。正解为两条路径同时走，每条路径都会涉及行列坐标的变化，因此总共有四个变化的坐标值需要标记状态，题目数据范围小，可以开四维 DP。
- 状态定义： dp[i][j][p][q] 表示第一条路径到达 (i, j)，第二条路径到达 (p, q) 时的最优解。
- 状态转移：分 4 种情况讨论两条路径分别到达（i，j）和 (p, q) 前一步的状态，取四种情况中的最大值再分别加上 a[i][j] 和 a[p][q] 即为 dp[i][j][p][q]。
- 第一条路径从上方转移来，第二条路径从上方转移来 -> dp[i-1][j][p-1][q];
- 第一条路径从上方转移来，第二条路径从左边转移来 -> dp[i-1][j][p][q-1];
- 第一条路径从左边转移来，第二条路径从左边转移来 -> dp[i][j-1][p][q-1];
- 第一条路径从左边转移来，第二条路径从上方转移来 -> dp[i][j-1][p-1][q];
- 注意：当某一时刻两条路径到达同一点(i == p 且 j == q)时，a[i][j] 与 a[p][q] 指向同一坐标值，该点可以分别被两条路径经过但是在取数总和中只能算一次，需特判减掉多算的一次。
代码
#include <bits/stdc++.h>
using namespace std;
int n, x, y, z, a[15][15], dp[15][15][15][15];
int main(){
cin >> n;
while(cin >> x >> y >> z && x){
a[x][y] = z;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int p = 1; p <= n; p++){
for(int q = 1; q <= n; q++){
dp[i][j][p][q] = a[i][j] + a[p][q] + max(
max(dp[i-1][j][p-1][q], dp[i-1][j][p][q-1]),
max(dp[i][j-1][p][q-1], dp[i][j-1][p-1][q]));
if(i == p && j == q) // 两条路径同时走到一个点
dp[i][j][p][q] -= a[i][j]; // 只算一次，减掉多余的
}
}
}
}
cout << dp[n][n][n][n];
return 0;
}
[NOIP2008 提高组] 传纸条
思路
- 本题和 [NOIP2000 提高组] 方格取数 类似，都是同时有两条路径要走，由于同一时刻两条路径移动的总步数是相同的，因此可以用走了多少步划分状态阶段，设当前走了 k 步，路径 1 走到第 x1 行，则其列数可推算出来为 (k – x1 + 2 列)，同理可求出路径 2 当前坐标：x2 行， (k – x2 + 2 列)。最外层枚举步数 k，内两层分别枚举两条路径的行数 x1 和 x2，进行状态转移求解。
- 求解时我们先假设会存在某个点被重复经过的情况，只在第一次经过时加上其好感值，下次就改为 0（相当于不加），而由于 a[i][j] >= 0，两条路径有重合点的情况必定不是最优的，会在转移过程中被自动舍弃。
- 状态定义： dp[k][x1][x2]: 走了 k 步的好感度最大值，路径 1 走到第 x1 行 (k – x1 + 2 列)，路径 2 走到第 x2 行 (k – x2 + 2 列) 。
- 状态转移：第 k 步的状态由第 k-1 步转移来，分四种情况讨论。
- 第一条路径从左边转移来，第二条路径从左边转移来 -> dp[k-1][x1][x2];
- 第一条路径从上方转移来，第二条路径从左边转移来 -> dp[k-1][x1-1][x2];
- 第一条路径从左边转移来，第二条路径从上方转移来 -> dp[k-1][x1][x2-1];
- 第一条路径从上方转移来，第二条路径从上方转移来 -> dp[k-1][x1-1][x2-1];
- 方程：dp[k][x1][x2] = a[x1][y1] + (x1 != x2 ? a[x2][y2] : 0) + max(max(dp[k-1][x1][x2], dp[k-1][x1-1][x2]), max(dp[k-1][x1][x2-1], dp[k-1][x1-1][x2-1]));
代码
#include <bits/stdc++.h>
using namespace std;
int n, m, a[55][55], dp[110][55][55];
/* dp[k][x1][x2]: 走了 k 步的好感度最大值，k 最大 n + m - 2 步。
路径 1 走到第 x1 行 (k - x1 + 2 列)，
路径 2 走到第 x2 行 (k - x2 + 2 列) */
int main(){
cin >> m >> n;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
cin >> a[i][j];
}
}
for(int k = 1; k <= n + m - 2; k++){ // 步数 k: 1 ~ n + m - 2 步
for(int x1 = 1; x1 <= m; x1++){ // 枚举路径 1 当前走到第 x1 行
for(int x2 = 1; x2 <= m; x2++){ // 枚举路径 2 当前走到第 x2 行
// 计算两条路径当前列数 y1，y2
int y1 = k - x1 + 2, y2 = k - x2 + 2;
if(y1 >= 1 && y1 <= n && y2 >= 1 && y2 <= n){ // 合法
dp[k][x1][x2] = a[x1][y1] +
(x1 != x2 ? a[x2][y2] : 0) + // 重合只加一次
max(max(dp[k-1][x1][x2], dp[k-1][x1-1][x2]),
max(dp[k-1][x1][x2-1], dp[k-1][x1-1][x2-1]));
}
}
}
}
cout << dp[n + m - 2][m][m];
return 0;
}