数据结构短视频 | 什么是动态规划
- 2019 年 12 月 23 日
- 笔记
前面，我们使用了数组、二分查找和分治算法解决了部分题目之后，还有更多的题目等着去挖掘。
我精力比较有限，不一定要把某数据结构的序列题目全部做完。如果你对某一个数据结构情有独钟的话，可以考虑接着去做下去，去发现更大的有趣的题目。
接下来，我们就做动态规划。
什么是动态规划？这可能属于分治算法。
因为动态规划用到了递归。。。。。。
了解动态规划之前，我们先了解什么是斐波那契数列。
如果看时间复杂度的话，发现这程序计算一个数字需要重复的计算。
比如n是5，需要计算4和3；计算4的话就需要计算3和2；计算3的话需要计算2和1……
可以发现5和4计算一次，3的话需要计算两次，浪费了一次资源，而2的话需要计算多次，就浪费了多次计算的资源。造成时间复杂度比较大。
所以需要考虑每一次需要计算的和计算的值保存到集合中，下面就是动态规划的代码：
动态规划就是：将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。
最后动态规划短视频：
——END——
