动态规划

“动态规划”这个名字其实起得不好，它的内核与”规划”不太相关，更像是分解。靠这种思路可以把可分解的问题更高效地解决——大多数时候这类问题本身就能写成递归，而 DP 强调的是子问题的”重叠”和”复用”。

背包问题

给定一组物品，每种物品有自己的重量和价格。在限定总重量的前提下，怎样选择才能让总价格最高？问题名来自如何把最合适的物品放进背包。

背包问题是 DP 的经典例子，因为它可以被描述为一个决策问题：在总重量不超过 W 的前提下，让总价值达到 V。

这类问题的难点是：每个物品都有”拿”或”不拿”两种状态，而每一个物品的最优决策又取决于其他物品的状态。光算性价比对它帮助甚微，需要更全局的考虑。

递归解

可以直接写递归——从第一个物品开始，对每一件考虑”包含”和”不包含”两种分支：

• 如果包含物品 n：在 总重量 - n 的重量、当前价值 + n 的价值、剩余物品集合 这个子问题下求最优解。
• 如果不包含物品 n：在 总重量、当前价值、剩余物品集合 这个子问题下求最优解。

每个无副作用的子问题都由三个参数刻画：剩余重量 W、当前价值 K、可用物品列表。三个参数完全决定了子问题的解。

动态规划

把上面这个递归 DP 化非常直接：只要子问题重叠且无副作用，DP 要做的就是把每个子问题的解缓存下来，下次相同参数的子问题来时直接读缓存。

那什么样的问题适合 DP？除了上面这些感性的说法，有没有清楚的判据？有的：

• 结构：子问题必须重叠，缓存的解才能在”参数相同 ⇒ 答案相同”的前提下被复用。注意这不等于”所有子问题都长得一样”——多个互相调用的函数也可以 DP，只要参数集合是可枚举的。
• 边界：问题必须有边界。这其实不是 DP 的前提，而是递归的前提——原问题必须像”从 n 个物品里选”这样有限，而不是”可以反复挑选某些”这样的无限可能。
• 独立：子问题的解仅由参数决定，不依赖外部状态。换句话说，参数完全确定能否复用缓存。