数据结构短视频 | 什么是动态规划

前面，我们使用了数组、二分查找和分治算法解决了部分题目之后，还有更多的题目等着去挖掘。

我精力比较有限，不一定要把某数据结构的序列题目全部做完。如果你对某一个数据结构情有独钟的话，可以考虑接着去做下去，去发现更大的有趣的题目。

接下来，我们就做动态规划。

什么是动态规划？这可能属于分治算法。

因为动态规划用到了递归。。。。。。

了解动态规划之前，我们先了解什么是斐波那契数列。

如果看时间复杂度的话，发现这程序计算一个数字需要重复的计算。

比如n是5，需要计算4和3；计算4的话就需要计算3和2；计算3的话需要计算2和1……

可以发现5和4计算一次，3的话需要计算两次，浪费了一次资源，而2的话需要计算多次，就浪费了多次计算的资源。造成时间复杂度比较大。

所以需要考虑每一次需要计算的和计算的值保存到集合中，下面就是动态规划的代码：

动态规划就是：将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

最后动态规划短视频：http://mpvideo.qpic.cn/0af25qn2yy2fyaymbyeqocqcaqcvrwwlurdhs7ipbifqkaqmbigq.f10002.mp4?dis_k=e2f80a4f437dab49d1ccf64436250e7f&dis_t=1577420028

——END——