【数据结构与算法】动态规划

很多人学背包问题时有一个共同困惑代码能背下来模板也记住了但换个题就不会了这说明你没有真正理解“背包问题”只是记住了“写法”。这篇文章的目标不是让你记住代码而是让你做到看到题 → 自己能推状态 → 自己能写转移一、先别急着学公式先搞清楚本质我们从最原始的问题开始有一些物品每个物品有重量和价值你有一个容量有限的背包怎么选才能价值最大如果不用动态规划你会怎么做方法一暴力枚举每个物品有两种选择选不选n 个物品 → 一共 2ⁿ 种情况你可以写递归int dfs(int i, int remain){ if(i n) return 0; // 不选 int res dfs(i1, remain); // 选前提放得下 if(remain w[i]){ res max(res, dfs(i1, remain - w[i]) v[i]); } return res; }这个思路是对的但复杂度是指数级。二、为什么需要动态规划来看这个递归dfs(i, remain)你会发现同一个(i, remain)会被计算很多次这就是“重复子问题”于是我们想到能不能把这些结果存起来这就是 DP 的来源。三、关键一步状态怎么定义很多人卡死在这一步。我们回到递归函数dfs(i, remain)直接把它“翻译”成 DPdp[i][j] 从第 i 个物品开始在剩余容量 j 下的最大价值或者更常见的写法dp[i][j] 前 i 个物品在容量 j 下的最大价值两种写法本质一样只是方向不同。四、状态转移是怎么“想出来”的现在我们站在 dp[i][j] 这个状态上意思是我现在有前 i 个物品背包容量是 j那第 i 个物品怎么办只有两种选择1. 不选第 i 个物品那价值就是dp[i-1][j]2. 选第 i 个物品前提j w[i]那你要腾出空间dp[i-1][j - w[i]] v[i]合并dp[i][j] max(不选, 选)也就是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])注意这一步不是背出来的是“分析出来的”。五、完整代码二维 DP#includeiostream #includevector using namespace std; int main(){ int n, W; cin n W; vectorint w(n1), v(n1); for(int i1;in;i){ cin w[i] v[i]; } vectorvectorint dp(n1, vectorint(W1, 0)); for(int i1;in;i){ for(int j0;jW;j){ // 不选 dp[i][j] dp[i-1][j]; // 选 if(j w[i]){ dp[i][j] max(dp[i][j], dp[i-1][j-w[i]] v[i]); } } } cout dp[n][W]; }六、最容易被忽略但最重要的一步优化很多人学到这里就结束了但真正面试中常用的是一维优化。为什么可以优化你看dp[i][j] 只依赖 dp[i-1][...]说明我们不需要存整张表只需要上一行优化成一维vectorint dp(W1, 0); for(int i1;in;i){ for(int jW;jw[i];j--){ dp[j] max(dp[j], dp[j-w[i]] v[i]); } }为什么一定要倒序这是很多人最容易写错的地方。如果你正序for(jw[i]; jW; j)那么dp[j-w[i]] 已经被更新过了相当于同一个物品被选了多次这就变成了完全背包七、完全背包区别到底在哪问题变成每个物品可以选无限次转移区别dp[j] max(dp[j], dp[j - w[i]] v[i])但这次for(int jw[i]; jW; j) // 正序为什么正序因为我希望 dp[j-w[i]] 是“当前轮更新过的”这样才能重复使用物品。八、你必须搞懂的核心区别非常重要类型是否可重复遍历方向01背包不可重复倒序完全背包可重复正序如果你只记住这一点已经能做 80% 背包题。九、再讲一个实战题真的常考题目分割等和子集能不能把数组分成两个和相等的部分转化如果总和是 sum能不能选一些数使和 sum / 2这就是 01 背包定义dp[j] 是否能凑出 j代码#includeiostream #includevector using namespace std; int main(){ int n; cin n; vectorint nums(n); int sum 0; for(int i0;in;i){ cinnums[i]; sum nums[i]; } if(sum % 2){ cout 0; return 0; } int target sum / 2; vectorbool dp(target1, false); dp[0] true; for(int i0;in;i){ for(int jtarget;jnums[i];j--){ dp[j] dp[j] || dp[j - nums[i]]; } } cout dp[target]; }十、背包问题其实只有这几种变化当你刷多了会发现所有题都在变这几个点1. 求最大值 → 普通背包2. 求方案数dp[j] dp[j-w[i]]3. 求是否存在dp[j] dp[j] || dp[j-w[i]]4. 多重背包每个物品有数量限制 → 转成多个 01 背包5. 分组背包每组选一个 → 多一层循环十一、真正刷题时的思考流程重点以后你遇到背包题按这个流程走第一步这是背包吗看特征有容量限制有选择求最大/最小/可行性第二步能不能重复选不能 → 01背包能 → 完全背包第三步dp 定义是什么最大值 → int是否存在 → bool方案数 → int累加第四步写转移永远是选 or 不选总结一句话背包问题本质就是在问在限制条件下怎么做选择最优。