动态规划

#动态规划

• 背包问题
• 动态规划
• 背包问题 FAQ
• 最长公共子串

#背包问题

假设你是个小偷，背着一个可装 4 磅东西的背包，可盗窃的商品有：

简单算法：尝试各种可能的商品组合。3 件商品需要计算 8 个集合，4 件商品需要 16 个，每增加一件翻倍。运行时间为 O(2ⁿ)，非常慢。

#动态规划

动态规划先解决子问题，再逐步解决大问题。每个动态规划算法都从一个网格开始。

背包问题的网格：各行为商品，各列为不同容量（1～4 磅）的背包。

填充吉他行：吉他重 1 磅，所有容量的背包都能装下，每个单元格填入吉他（1500 美元）。

填充音响行：音响重 4 磅。1～3 磅装不下，保持 1500。4 磅能装下音响，3000 > 1500，更新为 3000。

填充笔记本电脑行：笔记本电脑重 3 磅。1～2 磅装不下，保持 1500。3 磅能装下，2000 > 1500，更新为 2000。4 磅时：装笔记本电脑（3 磅），余下 1 磅，查之前 1 磅的最大价值是 1500（吉他），总计 2000+1500=3500 > 3000，更新为 3500。

答案：将吉他和笔记本电脑装入背包，价值最高为 3500 美元。

单元格值的计算公式：

cell[i][j] = max(
    上一行同一列的值（cell[i-1][j]），
    当前商品的价值 + cell[i-1][j - 当前商品的重量]
)

#背包问题 FAQ

• 再增加一件商品：只需在网格中添加一行，无需重新计算之前的结果。
• 行的排列顺序：无关紧要，结果相同。
• 可以逐列填充吗：就背包问题而言无影响，但其他问题可能有影响。
• 增加更小的商品（如 0.5 磅的项链）：需要调整网格的粒度，增加更多列。
• 可以偷商品的一部分吗：动态规划没法处理，但贪婪算法可以——按价值密度从高到低拿。
• 旅游行程最优化：这也是背包问题，约束条件从容量变成时间。
• 处理相互依赖的情况：动态规划无法处理。仅当每个子问题都是离散的（不依赖于其他子问题时）才管用。
• 最优解可能导致背包没装满：完全可能，比如偷了一颗 3.5 磅的钻石，余下 0.5 磅什么都装不下。

#最长公共子串

动态规划的另一个应用是找出两个字符串的最长公共子串（或最长公共子序列）。

假设用户输入了 hish，字典中有 fish 和 vista，要找出最接近的单词。建立网格比较 hish 和 fish：

如果两个字母相同，单元格值为左上方单元格的值加 1；否则为 0。最长公共子串长度为 3（"ish"）。

最长公共子序列：如果两个字母相同，值为左上方加 1；如果不同，取上方和左方的最大值。这种算法用于比较文件的差异（如 diff 命令）。

#动态规划小结

• 动态规划可帮助你在给定约束条件下找到最优解
• 在问题可分解为彼此独立且离散的子问题时，可使用动态规划
• 每种动态规划解决方案都涉及网格
• 单元格中的值通常就是你要优化的值
• 每个单元格都是一个子问题，考虑如何将问题分成子问题有助于找出网格的坐标轴
• 动态规划无法处理子问题相互依赖的情况
• 动态规划要么考虑拿走整件商品，要么不拿，无法处理拿走一部分的情况（用贪婪算法）