【动态规划之状态定义的技巧】
> 核心原则：状态需要完整描述当前局面，满足“无后效性”（过往的选择不会干扰后续决策），同时子问题能够重复使用。
> 一句话概括：状态记录「已经完成的操作、剩余的约束条件」，不保存完整过程细节。
✅ 技巧 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
