信息技术大学
二维 DP 与背包
数据结构与算法·面试高频 · 第 4 章 算法思想
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
二维 DP 与背包
数据结构与算法·面试高频 · 第 4 章 算法思想
01 背包与完全背包
每件一件 vs 无限件：转移只差遍历方向，一维优化靠逆序防重复。
01 背包
每件选或不选，一维容量逆序遍历
完全背包
物品无限件，一维容量正序允许重选
遍历顺序
逆序防同一件用两次，正序即表示允许
零钱兑换系列
凑金额最少几枚、共几种：完全背包换皮，组合与排列的遍历序不同。
最少硬币
dp[amt] = min(dp[amt−coin]+1)，不可达留 INF
组合数
外循环钱币内循环金额，不计顺序
排列数
外循环金额内循环钱币，顺序算数
最长公共子序列与编辑距离
两个字符串的二维 DP：相等取对角，不等取三方最小，编辑操作三选一。
LCS
字符相等取对角加一，否则取左右最大
编辑距离
增、删、改三方取最小，可滚动降维
应用
diff 工具、DNA 比对、模糊搜索
最长递增子序列及二分优化
O(n²) 经典到 O(n log n)：tails 数组存各长度 LIS 的最小结尾。
基础版
dp[i] = 前面更小值的 dp 最大加一
贪心加二分
tails 单调递增，新值二分替换或追加
tails 含义
长度 i 的 LIS 末尾最小值，保证最优子结构
本节要点
- ✓01 逆序，完全正序，方向即语义
- ✓零钱兑换：外循环定组合或排列
- ✓LCS 与编辑距离：对角与三方
- ✓LIS：tails 贪心加二分到 n log n
延伸主题：手写 01 背包一维版刷最长递增子序列
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
101 背包一维优化为什么必须逆序？
参考答案正序时 dp[j−c] 已是本轮更新过的值，等价于该物品被重复选取；逆序用的是上一轮旧值，保证每件只选一次。方向不是技巧，是语义。
2零钱兑换 II 求组合数，为什么外循环必须是钱币？
参考答案外循环钱币让每种面额在金额轴上成批进入，只数组合；若外循环金额，不同顺序被分别计数，数成了排列。遍历顺序决定计数语义。
3LIS 的二分优化为什么能保证正确？
参考答案tails[i] 记录「长度 i+1 的 LIS 的最小结尾」，可证其严格递增；新值替换第一个不小于它的位置，不破坏已有可行性，还让结尾更小、后路更宽。