2019-03-04
动态规划的名字起得不好，其内核与规划不同，更像是分解。使用动态规划的思想可以将可以分解的问题更简便的解决，大多数时候这种问题本身的解决方法就是递归，而动态规划更强调子问题的叠加和重复。
给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
背包问题用来当作动态规划的例子是十分合理的，因为它可以被描述为一个决定性的问题。有一个背包，我们如何能在总重量不超过 W 的前提下，使总价值达到 V。
这样的问题的难点是：每一个物品都有拿或者不拿两种可能，而任何一个物品的状态都要取决于其他的物品，计算性价比对这个问题效果甚为，需要更全局的考虑方式。
递归的做法是可行的，递归时从第一件物品开始，递归两种可能的结果，对于每一次计算都有如下可能。
假设我们分析是不是应该包含物品n：
总重量-n的重量，价值为当前价值+n的价值，物品为除去n的其他物品的前提下最优的方式。总重量，价值为当前价值，物品为除去n的其他物品的前提下最优的方式。通过这种方式，我们可以无限的递归下去，每一个没有副作用的子问题都包括三个参数重量W，价值K，可以用的物品列表，对于这样的问题，可以用动态规划的问题优化递归算法。
实际上，对于我们当前的递归解决方案的动态规划化是非常简单的，重点在子方法是否重叠，无副作用，如果是，那么实际上动态规划的要点就是保存每一个子问题的答案，并在重复我的问题出现时直接使用保存的结果。
那么什么样的问题可以使用动态规划解决呢，除了这些模糊的定义之外有没有标准的分界线呢？！ 有的！