本章导读
学习一个算法,可分为3个步骤:首先了解算法本身解决什么问题,然后学习它的解决策略,最后了解某些相似算法之间的联系。例如图算法中,
- 广搜是一层一层往外遍历,寻找最短路径,其策略是采取队列的方法。
- 最小生成树是最小代价连接所有点,其策略是贪心,比如Prim的策略是贪心+权重队列。
- Dijkstra是寻找单源最短路径,其策略是贪心+非负权重队列。
- Floyd是多结点对的最短路径,其策略是动态规划。
而贪心和动态规划是有联系的,贪心是“最优子结构+局部最优”,动态规划是“最优独立重叠子结构+全局最优”。一句话理解动态规划,则是枚举所有状态,然后剪枝,寻找最优状态,同时将每一次求解子问题的结果保存在一张“表格”中,以后再遇到重叠的子问题,从表格中保存的状态中查找(俗称记忆化搜索)。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「IT平头哥联盟」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程