动态规划之状态定义的技巧

【动态规划之状态定义的技巧】 > 核心原则：状态需要完整描述当前局面，满足“无后效性”（过往的选择不会干扰后续决策），同时子问题能够重复使用。 > 一句话概括：状态记录「已经完成的操作、剩余的约束条件」，不保存完整过程细节。 ✅ 技巧 1：提取题干约束，直接作为状态参数（最实用） 拿到题目，先提取题干中的限制条件，用作 dp 数组的下标。题目存在几个维度的约束，状态通常就设为几维。 例：洛谷 P1077：摆花（https://blog.csdn.net/hnjzsyjyj/article/details/166692286） 约束：①处理到第 i 种花；②总共摆放 j 盆花。 状态：dp[i][j] 表示前 i 种花，摆放 j 盆的方案总数。

#include <bits/stdc++.h>
using namespace std;

const int MOD=1e6+7;
const int N=1e2+5;
int dp[N][N];
int a[N];

int main() {
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>a[i];
}

dp[0][0]=1;
for(int i=1; i<=n; i++) {
for(int j=0; j<=m; j++) {
for(int k=0; k<=a[i] && k<=j; k++) {
dp[i][j]=(dp[i][j]+dp[i-1][j-k])%MOD;
}
}
}
cout<<dp[n][m]<<endl;
return 0;
}

/*
in:
2 4
3 2
out:
2
*/

✅ 技巧 2：仅保留必要信息，剔除冗余内容 状态下标数量越少越好，维度过多会造成时间、空间复杂度急剧上升。 无需记录全部历史选择，只保存会影响后续决策的关键信息。其本质就是保证无后效性：只要知道当前状态，就可以推导出后续结果，不必关心抵达该状态的路径。 例：AcWing 895：最长上升子序列（https://blog.csdn.net/hnjzsyjyj/article/details/149798835） （1）错误定义：dp[i] 存储前 i 个数的全部子序列（信息冗余） （2）正确定义：dp[i] 代表以第 i 个元素作为结尾的最长上升子序列长度 只保留结尾这个关键约束，前面的选取过程无需记录。

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e3+5;
int a[maxn],dp[maxn];
int ans=INT_MIN;
int n;

int main() {
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];

for(int i=1; i<=n; i++) {
dp[i]=1;
for(int j=1; j<i; j++) {
if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}

cout<<ans<<endl;
return 0;
}

/*
in:
7
3 1 2 1 8 5 6

out:
4
*/

✅ 技巧 3：目标对齐，所求即所存 题目要求求解什么，dp 数组的值就代表什么。 – 求方案总数：dp 存储方案数量 – 求最大 / 最小值：dp 存储最优价值 – 求最少操作次数：dp 存储最小步数 例：洛谷 P1002：过河卒（https://blog.csdn.net/hnjzsyjyj/article/details/138806060） 状态：设 dpf(i,j) 表示从 (0,0) 走到 (i,j) 的路径的条数。 如果 i=0 且 j=0，则 dp[i][j]=1； 否则，如果 i=0，则 dp[i][j]=dp[i][j−1]； 否则，如果 j=0，则 dp[i][j]=dp[i−1][j]； 否则，dp[i][j]=dp[i−1][j]+dp[i][j−1]。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn=25;
bool st[maxn][maxn];
LL dp[maxn][maxn];

int dx[]= {0,-2,-2,-1,-1,1,1,2,2};
int dy[]= {0,-1,1,-2,2,-2,2,-1,1};

int n,m,x,y;

int main() {
cin>>n>>m>>x>>y;
for(int i=0; i<9; i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0 && nx<=n && ny>=0 && ny<=m)
st[nx][ny]=true;
}

for(int i=0; i<=n; i++)
for(int j=0; j<=m; j++) {
if(st[i][j]) dp[i][j]=0;
else if(i==0 && j==0) dp[i][j]=1;
else if(i==0) dp[i][j]=dp[i][j-1];
else if(j==0) dp[i][j]=dp[i-1][j];
else dp[i][j]=dp[i-1][j]+dp[i][j-1];
}

cout<<dp[n][m];
}

/*
in:
8 6 0 4
out:
1617
——-
in:
6 6 3 2
out:
17
*/

✅ 技巧 4：优先采用前缀视角（背包、线性 DP 首选） 竞赛里大部分线性 DP、背包问题，优先使用“前缀视角”定义状态： dp[i] 表示“前 i 个物品全部决策完成后的结果”。 含义是前 i 个已经处理完毕，而非准备处理第 i 个。该视角天然适配「最后一步分析法」，便于推导状态转移方程。 例：洛谷 P2842：纸币问题 1（https://blog.csdn.net/hnjzsyjyj/article/details/166896877） 状态：dp[i][j] 表示考虑前 i 种纸币，凑出金额 j，所需要的最少纸币张数。 转移：dp[i][j]=min(dp[i-1][j], dp[i][j-ai]+1) 边界：dp[0][0]=0，其余 dp[0][j]=inf。

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=1e3+5;
const int W=1e4+5;
int dp[N][W];
int a[N];

int main() {
int n,w;
cin>>n>>w;
for(int i=1; i<=n; i++) {
cin>>a[i];
}

memset(dp,inf,sizeof dp);
dp[0][0]=0;
for(int i=1; i<=n; i++) {
for(int j=0; j<=w; j++) {
dp[i][j]=dp[i-1][j];
if(j>=a[i]) {
dp[i][j]=min(dp[i][j],dp[i][j-a[i]]+1);
}
}
}
cout<<dp[n][w]<<endl;
return 0;
}

/*
in:
6 15
1 5 10 20 50 100

out:
2
*/

✅ 技巧 5：遇到分支选择，增加 0/1 标记维度 当单纯一维状态无法描述当前局面、存在后效性时，增加一维 0/1 标记，记录二元开关状态，把两种不同局面分开存储，消除后效性。 例：AcWing 1055：股票买卖 II（https://blog.csdn.net/hnjzsyjyj/article/details/166903341） ● 状态定义 dp[i][0]：第 i 天结束时，不持有股票的最大收益 dp[i][1]：第 i 天结束时，持有股票的最大收益 ● 转移分析（最后一步分析法） 1. dp[i][0]：第 i 天不持有股票。两种来源：    – 前一天本来就不持有，今天什么都不做：dp[i-1][0]    – 前一天持有股票，今天卖出：dp[i-1][1] + a[i] dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]) 2. dp[i][1]：第 i 天持有股票。两种来源：    – 前一天已经持有，今天不动：dp[i-1][1]    – 前一天无股票，今天买入：dp[i-1][0]-a[i] dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i]) ● 边界： dp[0][0]=0：第 0 天，无股票，收益 0 dp[0][1]=-inf：第 0 天不可能持有股票，负无穷（非法状态） ● 最终答案：dp[n][0]，最后一天一定不持有股票（卖出才兑现利润）

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=1e5+5;
int dp[N][2];
int a[N];

int main() {
int n;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
}

dp[0][0]=0, dp[0][1]=-inf;
for(int i=1; i<=n; i++) {
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i]);
}
cout<<dp[n][0]<<endl;
return 0;
}

/*
in:
6
7 1 5 3 6 4

out:
7
*/

✅ 技巧 6：校验：用无后效性反向检验状态是否合格 检验标准：给定当前状态，能否独立计算后续所有结果，无需关注抵达该状态的路径？ – 可以：状态定义合格； – 不行：状态缺少关键信息，需要补充维度。 【动态规划状态转移方程推导的经典方法】 ✅ 方法 1：最后一步法（推荐）：https://www.bilibili.com/video/BV1xb411e7ww 最后一步法（末端分析法），不去从头模拟整个过程，只看结尾的决策。即：先定义状态，再思考 “最后一步发生了什么”，最后写出转移。最后一步法是竞赛最常用、上手最快的方法。 ✅ 方法 2：子集划分法（区间 DP，石子合并、括号匹配） 区间 DP 处理一段连续区间上的问题，核心思路为“把一个大的连续区间，通过一次分割拆成左右两段互不干扰的子区间；大区间的最优解，由这两个子区间的结果合并计算得到”。 注意：每次分割只切一刀，得到两个子区间；子区间可以继续递归分割，不断拆成更小的两段，直到区间长度为 1（边界）。 状态定义：dp[l][r] 表示区间 [l,r] 内的最优解。 我们枚举分割点 k（l≤k<r），把区间 [l,r] 在 k 的位置切开，得到左区间 [l,k]、右区间 [k+1,r]。左右子区间独立求解，再合并结果。遍历全部合法分割点，选出最优值。 对所有合法分割点取最优值，得到大区间答案：dp[l][r]=min(dp[l][k]+dp[k+1][r]) ✅ 方法 3：增量递推法（简单线性 DP，最长上升子序列 LIS） 增量递推法适用于线性序列问题，核心思路为“从左往右逐个新增元素，以当前元素作为子序列的结尾，在前面已经求解完成的子问题基础上，更新当前状态”。 状态定义：dp[i] 表示以序列中第 i 个元素作为结尾的最长上升子序列的长度。 ✅ 闫氏 DP 分析法：https://www.bilibili.com/video/BV1X741127ZM