第五章导读

学习一个算法，先知其解决什么，后知其解决策略，最后了解彼此之间的联系。如图算法中，

• ①广搜：一层一层往外遍历，寻找最短路径，策略：队列，
• ②最小生成树：最小代价连接所有点，策略：贪心（Prim：贪心+权重队列），
• ③Dijkstra：寻找单源最短路径，策略：贪心+非负权重队列，
• ④Floyd：多结点对的最短路径，策略：动态规划。

而贪心和动态规划之间的联系是，贪心：最优子结构+局部最优，动态规划：最优独立重叠子结构+全局最优。故一句话理解动态规划则是枚举所有状态，然后剪枝，找到最优状态，保存，以后再遇到重叠的子问题，从保存的状态中搜索（俗称记忆化搜索）。