动态规划

为什么会用动态规划，当碰到类似背包问题时，有多个最优目标。这时候如果使用决策树或者分治搜索遍历所有解，会导致重复计算，因为有些子问题相同。所以转换思路，从子问题的增长到最终问题来解决问题。这过程中要定义子问题的状态转移，也就是递推式。

可以用记忆搜索进行递归实现递推式的计算。但是要递归的空间消耗。

使用动态规划则是从小到大记录问题的状态，这个状态的值即结果，状态则根据问题而定义，如背包问题，状态是装到第几个物品和背包重量，对应的值是背包价值。那么只需要找装物品的序号和背包重量的选择对背包价值的影响即可。

进一步，动态规划记录的 dp 数组其实就是记忆搜索存储的内容么，这么看空间消耗好像除了递归的消耗之外没有什么差别。再进一步，如果 dp 数组的计算并不会用到整个数组，只是相邻的几个值，那么就可以用一个很小的数组解决问题。

重叠子问题：可以用递归解决
最优子结构：原问题解由子问题最优解构建，这就有点类似夸大事实的谬误（不好好读书，就会当乞丐，这里是夸大了危害的事实，也就是危害作为优化的目标）
无后效性：即类似马尔可夫的性质，即可以把过去发生的事件，累积起来看，而不会影响后续事件的计算。

• 如果无法满足后效性，可以尝试添加过去发生事件之间的约束到状态累积中，把这些全部当成一个状态积累。如背包问题中有两种物品，每两次选择必须交替类型，那么把两次选择当成一次 dp 计算，本质是加了约束的动态规划。

技巧：

• 边界条件拿来初始化 dp 数组
• 具体实现，根据计算顺序遍历填充 dp 数组即可
• 空间优化：
  • 背包问题，每次选择放入只与上次有关，那么 dp 数组只要保存一行即可（但是要倒序遍历，不然会覆盖了）。