15｜课程回顾与总结（上）
卢誉声
你好，我是卢誉声。
当你看到这里的时候，说明你已基本学习完了我们的整个专栏。在经过一系列的课程之后，你应该已经对最难技术面试问题——动态规划，有了较为全面的认识，并且知道该如何去解决一些经典的问题和这些问题的变种。
话说回来，无论你是按部就班学习完整个专栏，还是有所挑选地进行阅读，我都建议你认真读完本节课和下节课的内容。就如标题所写，这两节课主要是对整个专栏的内容进行回顾与总结，会涵盖有关动态规划的重要内容。
如果你认真学完了本专栏的所有内容，掌握了动态规划的基本概念，能够熟练解决动态规划的经典问题，你仍然可以通过这两节课来进行查漏补缺；而如果你在之前的课程中还是有所疑惑，那么你还可以利用总结中的梳理来掌握动态规划最核心的知识点和内容，再回去认真学习相关内容，我相信你会有更多收获。
好了，现在就让我们开始吧。
从贪心算法到动态规划
1. 贪心算法
在详细讲解动态规划之前，我们势必要从贪心算法说起。
无论是使用动态规划还是其它的任何算法，核心目的就是求出问题的最优解，只不过具体的思路和方法技巧会有所区别。在解决任何最优解问题的时候我们基本都绕不开一组概念，就是局部最优解和整体最优解。
局部最优解：针对一定条件或环境下的一个问题或目标，是部分解决该问题决策中的最优决策，也就是一个问题的解在一定范围或区域内最优，或者说解决问题或达成目标的手段在一定范围或限制内最优；
整体最优解：针对一定条件或环境下的一个问题或目标，是所有解决该问题决策中的最优决策。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了动态规划在解决硬币找零问题中的应用，并重点回顾了贪心算法和动态规划的关系。文章首先介绍了贪心算法的局部最优解和整体最优解的概念，以及在硬币找零问题中的应用。然后指出了贪心算法的局限性，需要引入回溯和递归的过程来寻找整体最优解。讨论了递归算法的指数级时间复杂度和剪枝优化的重要性，以及贪心算法作为一种剪枝优化思路的局限性。强调了动态规划作为一种更加全面的解决方案，能够解决贪心算法无法解决的问题，并提出了动态规划的优势和适用性。文章通过对贪心算法和动态规划的讨论，展现了动态规划作为一种更加全面、灵活的解决方案，能够解决贪心算法无法解决的问题，为读者提供了对动态规划的全面认识和理解。文章还详细分析了动态规划的特性和解题思路，为读者提供了解决动态规划面试问题的通用框架。整体而言，本文通过深入的技术讨论，使读者能够快速了解动态规划的应用和特点，为解决类似问题提供了有益的指导。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《动态规划面试宝典》，新⼈⾸单¥59
《动态规划面试宝典》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(4)
- 最新
- 精选
宋不肥https://alchemist-al.com/algorithms/longest-common-subsequence 推荐给坚持完课程的小伙伴一个链接，里面有很多dp的动图表，无聊时玩玩还是挺有意思的。有点类似老师之前画的那个表作者回复: 一个不错的补充。
2020-11-265
norton/Dark
感觉要开窍了，辛苦了卢老师作者回复: 开窍了就意味着离掌握动归这门奥义不远了，如果可能的话，做一些练习，再回顾一下课程，就能尽快实现目标～
2020-10-223- Geek_606c63这一节终于弄懂了很多之前模糊的概念，和上面的同学一样，感觉要开窍了。
作者回复: 有时候反复琢磨一下这些概念，慢慢就融会贯通了。多思考，最后其实发现概念就那么几个。套套模板就能解决大多数问题。
2021-09-22 
有手也不行去年九月买的课，今年七月开始看，终于完结撒花了，老师讲的真的好，比我看leetcoe题解强了不知道多少倍(狗头.jpg)，最重要是真的感觉和楼上那个兄弟一样开窍了。作者回复: 感谢你的认可！你的认可就是对我和课程的最大鼓励！
2021-07-26
收起评论
