Skip to content

Latest commit

 

History

History
138 lines (96 loc) · 9.77 KB

动态规划总结篇.md

File metadata and controls

138 lines (96 loc) · 9.77 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!

动态规划最强总结篇!

如今动态规划已经讲解了42道经典题目,共50篇文章,是时候做一篇总结了。

关于动态规划,在专题第一篇关于动态规划,你该了解这些!就说了动规五部曲,而且强调了五部对解动规题目至关重要!

这是Carl做过一百多道动规题目总结出来的经验结晶啊,如果大家跟着「代码随想录」刷过动规专题,一定会对这动规五部曲的作用感受极其深刻。

动规五部曲分别为:

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

动规专题刚开始的时候,讲的题目比较简单,不少录友和我反应:这么简单的题目 讲的复杂了,不用那么多步骤分析,想出递推公式直接就AC这道题目了。

Carl的观点一直都是 简单题是用来 巩固方法论的。 简单题目是可以靠感觉,但后面稍稍难一点的题目,估计感觉就不好使了。

在动规专题讲解中,也充分体现出,这动规五部曲的重要性。

还有不少录友对动规的理解是:递推公式是才是最难最重要的,只要想出递归公式,其他都好办。

其实这么想的同学基本对动规理解的不到位的

动规五部曲里,哪一部没想清楚,这道题目基本就做不出来,即使做出来了也没有想清楚,而是朦朦胧胧的就把题目过了。

  • 如果想不清楚dp数组的具体含义,递归公式从何谈起,甚至初始化的时候就写错了。
  • 例如动态规划:不同路径还不够,要有障碍! 在这道题目中,初始化才是重头戏
  • 如果看过背包系列,特别是完全背包,那么两层for循环先后顺序绝对可以搞懵很多人,反而递归公式是简单的。
  • 至于推导dp数组的重要性,动规专题里几乎每篇Carl都反复强调,当程序结果不对的时候,一定要自己推导公式,看看和程序打印的日志是否一样。

好啦,我们再一起回顾一下,动态规划专题中我们都讲了哪些内容。

动态规划基础

背包问题系列

背包问题大纲

打家劫舍系列

股票系列

股票问题总结

子序列系列

动规结束语

关于动规,还有 树形DP(打家劫舍系列里有一道),数位DP,区间DP ,概率型DP,博弈型DP,状态压缩dp等等等,这些我就不去做讲解了,面试中出现的概率非常低。

能把本篇中列举的题目都研究通透的话,你的动规水平就已经非常高了。 对付面试已经足够!

这个图是 代码随想录知识星球 成员:,所画,总结的非常好,分享给大家。

这应该是全网对动规最深刻的讲解系列了。

其实大家去网上搜一搜也可以发现,能把动态规划讲清楚的资料挺少的,因为动规确实很难!要给别人讲清楚更难!

《剑指offer》上 动规的题目很少,经典的算法书籍《算法4》 没有讲 动规,而《算法导论》讲的动规基本属于劝退级别的。

讲清楚一道题容易,讲清楚两道题也容易,但把整个动态规划的各个分支讲清楚,每道题目讲通透,并用一套方法论把整个动规贯彻始终就非常难了。

所以Carl花费的这么大精力,把自己对动规算法理解 一五一十的全部分享给了录友们,帮助大家少走弯路,加油!