动态规划

本章导读

学习一个算法，可分为3个步骤：首先了解算法本身解决什么问题，然后学习它的解决策略，最后了解某些相似算法之间的联系。例如图算法中，

• 广搜是一层一层往外遍历，寻找最短路径，其策略是采取队列的方法。
• 最小生成树是最小代价连接所有点，其策略是贪心，比如Prim的策略是贪心+权重队列。
• Dijkstra是寻找单源最短路径，其策略是贪心+非负权重队列。
• Floyd是多结点对的最短路径，其策略是动态规划。

而贪心和动态规划是有联系的，贪心是“最优子结构+局部最优”，动态规划是“最优独立重叠子结构+全局最优”。一句话理解动态规划，则是枚举所有状态，然后剪枝，寻找最优状态，同时将每一次求解子问题的结果保存在一张“表格”中，以后再遇到重叠的子问题，从表格中保存的状态中查找（俗称记忆化搜索）。