动态规划————将问题分为小问题，并先着手解决这些小问题。动态规划和分而治之的不同在于，分而治之需要在计算每个子问题的时候都进行一边计算，而动态规划则更多是范围变大的子问题与之前的更小范围的子问题的结果进行比较。
第九章 动态规划
背包问题
有限容量内如何装价值最高的商品组合。
简单算法
尝试所有可能的组合，并找出价值最高的组合。
动态规划
动态规划先解决子问题，再逐步解决大问题。
针对背包问题，在增加可选商品的单次循环中，逐步增加背包容量，找出当次循环最大价值组合的方式，查找最优解。 如：
- 吉他可选时，容量从1到4，找出最优组合；
- 吉他、音响可选时，容量从1到4，找出最优解；
- 一直到所有商品可选时，容量从1到4，找出最优解。
例： 背包最大容量为4磅
- A 4磅 3000美元
- B 3磅 2000美元
- C 1磅 1500美元
| 商品 | 1 | 2 | 3 | 4 | 备注 | |
|---|---|---|---|---|---|---|
| A | x:0 | x:0 | x:0 | A:3000 | 可选A | |
| B | x:0 | x:0 | B:2000 | A:3000 | 可选AB | |
| C | C:1500 | C:1500 | B:2000 | C+B:1500+2000 > 3000 | 可选ABC |
每格中为当前最优解
为什么要拆成子问题，因为在这个过程中我们其实使用了这种比较方式：
cell[i][j] = max(cell[i-1][j], 当前行商品价值+cell[i-1][i-当前行商品重])
而比较的值其实就是小问题的最优解。
一些结论
- 沿着列向下走时，最大价值不会降低，每次迭代，都会存储当前的最大价值。
- 行的排列顺序变化不会影响结果，我们上方的例子与书中的求解顺序就不相同。
- 交换行和列的值进行迭代可能会影响结果。
- 根据新商品的增加可能要考虑更细粒度的方法，调整网格结构，如由1磅的迭代调整为0.5磅的迭代。
- 考虑拿走商品的一部分时无法使用动态规划，使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而无法判断该不该拿走多大部分，这个时候可以使用贪婪算法。
- 当可选项中出现依赖关系时，如选了一件商品会影响其他商品价值时，无法使用动态规划，仅当每格子问题都是离散的，即不依赖于其他子问题，动态规划才生效。
- 计算最终解时，只会直接比较两个子问题的结果。
- 最优解可能导致背包没装满。
最长公共子串
另一个应用实例，不在记录。
小结
- 需要在给定约束条件下优化某种指标时，动态规划很有用。
- 问题可分解为离散子问题时，可使用动态规划来解决。
- 每种动态规划解决方案都设计网格。
- 单元格中的值通常就是你要优化的值。
- 每格单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
- 没有放之四海皆准的计算动态规划解决方案的公式。