DP维度思考简记（不喜就喷）
2026-05-12 20:06:18
发布于：北京
我才六年级，我还不太熟悉dp呢，喷可以，但喷轻点谢谢
还有本篇未使用标准的Markdown规范文章模板及LaTeX，不要骂！
在做dp题目时，常常会遇到正常定义无法解决的问题
这里就拿一些例题随便聊聊
-
如何确定dp数组的维度与含义？
个人认为着重考虑会对最终答案造成影响的方案/条件 -
推导相应的状态转移方程
可以考虑以下几个方面- 数组有几维？
- 每个维度表示什么？存储什么信息？
- 转移过程中信息不够，缺乏关键信息 -> 考虑扩维
- 空间复杂度过高 -> 考虑降维（或许也可以优化）
对于这道例题，会发现如果将dp[i][j]定义为以a[i][j]为右下角的最大正方形边长，实际上无法确定“01交替是否可行”（个人随意起的名字）。因此需考虑扩维
个人认为，扩维没有标准的方法，思维在这时就尤为重要，思维发散一点，或许可以得到一些收获
所以，这题扩一个维度即可，设置dp[i][j][0/1]为以(i,j)为右下角点且当前点的颜色为0/1的最大正方形边长
因此，答案一目了然
如果当前这一位是0，则左边及上边的颜色应为1，左上角点应为0
如果当前这一位是1，则左边及上边的颜色应为0，左上角点应为1
代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1555;
int a[N][N];
int dp[N][N][2];
int main(){
memset(dp, 0, sizeof(dp));
cin >> n >> m;
for (int i = 1;i <= n;i++){
for (int j = 1;j <= m;j++){
cin >> a[i][j];
}
}
for (int i = 1;i <= n;i++){
for (int j = 1;j <= m;j++){
if (a[i][j] == 0){
dp[i][j][0] = min({dp[i - 1][j][1], dp[i][j - 1][1], dp[i - 1][j - 1][0]}) + 1;
}
if (a[i][j] == 1){
dp[i][j][1] = min({dp[i - 1][j][0], dp[i][j - 1][0], dp[i - 1][j - 1][1]}) + 1;
}
}
}
int mx = INT_MIN;
for (int i = 1;i <= n;i++){
for (int j = 1;j <= m;j++){
// cout << dp[i][j][0] << " " << dp[i][j][1] << endl;
mx = max({mx, dp[i][j][0], dp[i][j][1]});
}
}
cout << mx;
return 0;
}
例题在这里：最大正方形II
新题开始：
对于这道例题，会发现如果将dp[i]定义为前i个数字变为非递减的最小操作次数，实际上无法确定“a[i - 1]此时是多少”（个人随意起的名字）。因此需考虑扩维
所以，这题扩维即可，设置dp[i][j(-1/0/1)]为以(i,j)为前i个数字，最后一个数字（也就是第i-1个数字）是j时，变为非递减的最小操作次数
因此，答案一目了然
状态转移方程不推导了，因为本篇主要分享维度思考
代码
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1111111;
int a[N];
int dp[N][3];
int main(){
cin >> n;
for (int i = 1;i <= n;i++){
cin >> a[i];
}
memset(dp, 0x3f, sizeof(dp));
dp[1][a[1] + 1] = 0;
for (int i = 2;i <= n;i++){
if (a[i] == 1){
dp[i][0] = dp[i - 1][0] + 2;
dp[i][1] = dp[i - 1][0] + 1;
dp[i][2] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
} else if (a[i] == 0){
dp[i][0] = dp[i - 1][0] + 1;
dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]);
dp[i][2] = dp[i - 1][2] + 1;
} else {
dp[i][0] = dp[i - 1][0];
dp[i][2] = dp[i - 1][2] + 2;
}
}
if (min({dp[n][0],dp[n][1],dp[n][2]}) == dp[0][0]){
cout << "BRAK";
return 0;
}
cout << min({dp[n][0], dp[n][1], dp[n][2]});
return 0;
}
例题在这里： BAJ-Bytecomputer
新题开始：
题面较长，限制条件较多（但是这反而更简单？）
第一眼看到这题：简单，max就行了，第二眼：咋有如此之多限制条件？
对于这道例题，会发现如果将dp[i]定义为前i个点种满树的最大观赏值，实际上无法确定“前一项到底是多高的树”（个人随意起的名字）。因此需考虑扩维
第一次扩维：
dp[i][j(0/1/2)]表示前i个点种满树且最后一个点种的树为j时的最大观赏价值。0/1/2分别代表低中高树。
但是这里还是无法确定“i和前面点的高低关系”，如果第i个点比第i-1个点高，下一个就必须要下降，反之则亦然。
继续扩维
dp[i][j(0/1/2)][k(0/1)]
dp[i][j][k] 表示前i棵树所能达到的最大观赏价值和，最后一个点种的树是j，表示第i棵树比左右两棵树都高（k=1）,否则相反(k=0)
不过这里还有问题，目前的想法无法实现“环形”，毕竟这次咱们交流维度，继续扩维！
简单来讲，第四个维度就是记录“第一棵树是啥”，这样更好解决“环形”的问题
最终：
dp[i][j][k][l]代表：
考虑前i棵树
最后一棵树高度为j(0/1/2分别代表低中高树)
最后一棵树比它前面的和后面的状态(0代表低,1代表高)
第一棵树的高度为l(0/1/2分别代表低中高树)
时可获得的最大价值
因此，答案一目了然
状态转移方程不推导了，因为本篇主要分享维度思考
代码
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5 + 10;
int a[N][3];
int dp[N][3][2][3];
/*
dp[i][j][k][l]代表：
考虑前i棵树
最后一棵树高度为j(0/1/2分别代表低中高树)
最后一棵树比它前面的和后面的状态(1代表低,0代表高)
第一棵树的高度为l(0/1/2分别代表低中高树)
时可获得的最大价值
*/
int main(){
cin >> n;
for (int i = 1;i <= n;i++){
cin >> a[i][0] >> a[i][1] >> a[i][2];
}
// 初始化
dp[1][0][1][0] = a[1][0];
dp[1][1][0][1] = a[1][1];
dp[1][1][1][1] = a[1][1];
dp[1][2][0][2] = a[1][2];
// 状态转移
for (int i = 2;i <= n;i++){
for (int j = 0;j <= 2;j++){// j循环作用不大，主要用于持续转移dp[][][][l]
dp[i][0][1][j] = max(dp[i - 1][1][0][j], dp[i - 1][2][0][j]) + a[i][0];
dp[i][1][0][j] = dp[i - 1][0][1][j] + a[i][1];
dp[i][1][1][j] = dp[i - 1][2][0][j] + a[i][1];
dp[i][2][0][j] = max(dp[i - 1][1][1][j], dp[i - 1][0][1][j]) + a[i][2];
}
}
// 得到结果（只考虑合法状态（环形要求！））
int mx = max({dp[n][0][1][1], dp[n][0][1][2], dp[n][1][0][0], dp[n][1][1][2], dp[n][2][0][1], dp[n][2][0][0]});
cout << mx;
return 0;
}
有帮助，赞一个