【动态规划之状态定义的技巧】 核心原则状态需要完整描述当前局面满足“无后效性”过往的选择不会干扰后续决策同时子问题能够重复使用。 一句话概括状态记录「已经完成的操作、剩余的约束条件」不保存完整过程细节。✅ 技巧 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 MOD1e67; const int N1e25; int dp[N][N]; int a[N]; int main() { int n,m; cinnm; for(int i1; in; i) { cina[i]; } dp[0][0]1; for(int i1; in; i) { for(int j0; jm; j) { for(int k0; ka[i] kj; k) { dp[i][j](dp[i][j]dp[i-1][j-k])%MOD; } } } coutdp[n][m]endl; return 0; } /* in: 2 4 3 2 out: 2 */✅ 技巧 2仅保留必要信息剔除冗余内容状态下标数量越少越好维度过多会造成时间、空间复杂度急剧上升。无需记录全部历史选择只保存会影响后续决策的关键信息。其本质就是保证无后效性只要知道当前状态就可以推导出后续结果不必关心抵达该状态的路径。例AcWing 895最长上升子序列https://blog.csdn.net/hnjzsyjyj/article/details/1497988351错误定义dp[i] 存储前 i 个数的全部子序列信息冗余2正确定义dp[i] 代表以第 i 个元素作为结尾的最长上升子序列长度只保留结尾这个关键约束前面的选取过程无需记录。#include bits/stdc.h using namespace std; const int maxn1e35; int a[maxn],dp[maxn]; int ansINT_MIN; int n; int main() { cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) { dp[i]1; for(int j1; ji; j) { if(a[j]a[i]) dp[i]max(dp[i],dp[j]1); } ansmax(ans,dp[i]); } coutansendl; 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) 的路径的条数。如果 i0 且 j0则 dp[i][j]1否则如果 i0则 dp[i][j]dp[i][j−1]否则如果 j0则 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 maxn25; 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() { cinnmxy; for(int i0; i9; i) { int nxxdx[i]; int nyydy[i]; if(nx0 nxn ny0 nym) st[nx][ny]true; } for(int i0; in; i) for(int j0; jm; j) { if(st[i][j]) dp[i][j]0; else if(i0 j0) dp[i][j]1; else if(i0) dp[i][j]dp[i][j-1]; else if(j0) dp[i][j]dp[i-1][j]; else dp[i][j]dp[i-1][j]dp[i][j-1]; } coutdp[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纸币问题 1https://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 inf0x3f3f3f3f; const int N1e35; const int W1e45; int dp[N][W]; int a[N]; int main() { int n,w; cinnw; for(int i1; in; i) { cina[i]; } memset(dp,inf,sizeof dp); dp[0][0]0; for(int i1; in; i) { for(int j0; jw; j) { dp[i][j]dp[i-1][j]; if(ja[i]) { dp[i][j]min(dp[i][j],dp[i][j-a[i]]1); } } } coutdp[n][w]endl; return 0; } /* in: 6 15 1 5 10 20 50 100 out: 2 */✅ 技巧 5遇到分支选择增加 0/1 标记维度当单纯一维状态无法描述当前局面、存在后效性时增加一维 0/1 标记记录二元开关状态把两种不同局面分开存储消除后效性。例AcWing 1055股票买卖 IIhttps://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 天无股票收益 0dp[0][1]-inf第 0 天不可能持有股票负无穷非法状态● 最终答案dp[n][0]最后一天一定不持有股票卖出才兑现利润#include bits/stdc.h using namespace std; const int inf0x3f3f3f3f; const int N1e55; int dp[N][2]; int a[N]; int main() { int n; cinn; for(int i1; in; i) { cina[i]; } dp[0][0]0, dp[0][1]-inf; for(int i1; in; 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]); } coutdp[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] 内的最优解。我们枚举分割点 kl≤kr把区间 [l,r] 在 k 的位置切开得到左区间 [l,k]、右区间 [k1,r]。左右子区间独立求解再合并结果。遍历全部合法分割点选出最优值。对所有合法分割点取最优值得到大区间答案dp[l][r]min(dp[l][k]dp[k1][r])✅ 方法 3增量递推法简单线性 DP最长上升子序列 LIS增量递推法适用于线性序列问题核心思路为“从左往右逐个新增元素以当前元素作为子序列的结尾在前面已经求解完成的子问题基础上更新当前状态”。状态定义dp[i] 表示以序列中第 i 个元素作为结尾的最长上升子序列的长度。✅ 闫氏 DP 分析法https://www.bilibili.com/video/BV1X741127ZM
动态规划之状态定义的技巧
【动态规划之状态定义的技巧】 核心原则状态需要完整描述当前局面满足“无后效性”过往的选择不会干扰后续决策同时子问题能够重复使用。 一句话概括状态记录「已经完成的操作、剩余的约束条件」不保存完整过程细节。✅ 技巧 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 MOD1e67; const int N1e25; int dp[N][N]; int a[N]; int main() { int n,m; cinnm; for(int i1; in; i) { cina[i]; } dp[0][0]1; for(int i1; in; i) { for(int j0; jm; j) { for(int k0; ka[i] kj; k) { dp[i][j](dp[i][j]dp[i-1][j-k])%MOD; } } } coutdp[n][m]endl; return 0; } /* in: 2 4 3 2 out: 2 */✅ 技巧 2仅保留必要信息剔除冗余内容状态下标数量越少越好维度过多会造成时间、空间复杂度急剧上升。无需记录全部历史选择只保存会影响后续决策的关键信息。其本质就是保证无后效性只要知道当前状态就可以推导出后续结果不必关心抵达该状态的路径。例AcWing 895最长上升子序列https://blog.csdn.net/hnjzsyjyj/article/details/1497988351错误定义dp[i] 存储前 i 个数的全部子序列信息冗余2正确定义dp[i] 代表以第 i 个元素作为结尾的最长上升子序列长度只保留结尾这个关键约束前面的选取过程无需记录。#include bits/stdc.h using namespace std; const int maxn1e35; int a[maxn],dp[maxn]; int ansINT_MIN; int n; int main() { cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) { dp[i]1; for(int j1; ji; j) { if(a[j]a[i]) dp[i]max(dp[i],dp[j]1); } ansmax(ans,dp[i]); } coutansendl; 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) 的路径的条数。如果 i0 且 j0则 dp[i][j]1否则如果 i0则 dp[i][j]dp[i][j−1]否则如果 j0则 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 maxn25; 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() { cinnmxy; for(int i0; i9; i) { int nxxdx[i]; int nyydy[i]; if(nx0 nxn ny0 nym) st[nx][ny]true; } for(int i0; in; i) for(int j0; jm; j) { if(st[i][j]) dp[i][j]0; else if(i0 j0) dp[i][j]1; else if(i0) dp[i][j]dp[i][j-1]; else if(j0) dp[i][j]dp[i-1][j]; else dp[i][j]dp[i-1][j]dp[i][j-1]; } coutdp[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纸币问题 1https://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 inf0x3f3f3f3f; const int N1e35; const int W1e45; int dp[N][W]; int a[N]; int main() { int n,w; cinnw; for(int i1; in; i) { cina[i]; } memset(dp,inf,sizeof dp); dp[0][0]0; for(int i1; in; i) { for(int j0; jw; j) { dp[i][j]dp[i-1][j]; if(ja[i]) { dp[i][j]min(dp[i][j],dp[i][j-a[i]]1); } } } coutdp[n][w]endl; return 0; } /* in: 6 15 1 5 10 20 50 100 out: 2 */✅ 技巧 5遇到分支选择增加 0/1 标记维度当单纯一维状态无法描述当前局面、存在后效性时增加一维 0/1 标记记录二元开关状态把两种不同局面分开存储消除后效性。例AcWing 1055股票买卖 IIhttps://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 天无股票收益 0dp[0][1]-inf第 0 天不可能持有股票负无穷非法状态● 最终答案dp[n][0]最后一天一定不持有股票卖出才兑现利润#include bits/stdc.h using namespace std; const int inf0x3f3f3f3f; const int N1e55; int dp[N][2]; int a[N]; int main() { int n; cinn; for(int i1; in; i) { cina[i]; } dp[0][0]0, dp[0][1]-inf; for(int i1; in; 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]); } coutdp[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] 内的最优解。我们枚举分割点 kl≤kr把区间 [l,r] 在 k 的位置切开得到左区间 [l,k]、右区间 [k1,r]。左右子区间独立求解再合并结果。遍历全部合法分割点选出最优值。对所有合法分割点取最优值得到大区间答案dp[l][r]min(dp[l][k]dp[k1][r])✅ 方法 3增量递推法简单线性 DP最长上升子序列 LIS增量递推法适用于线性序列问题核心思路为“从左往右逐个新增元素以当前元素作为子序列的结尾在前面已经求解完成的子问题基础上更新当前状态”。状态定义dp[i] 表示以序列中第 i 个元素作为结尾的最长上升子序列的长度。✅ 闫氏 DP 分析法https://www.bilibili.com/video/BV1X741127ZM
