DP(动态规划)到底是什么？
2020-05-11 本文已影响0人
快乐自由拉菲犬
贪心学院NLP的课程中，老师一再强调DP很重要很重要。但是究竟DP是个啥？
在bilibili找了好多视频，都是以小时计数的，不想啰嗦啊，就想知道DP到底是个啥？要干啥？而不是理解一大堆复杂的概念直接陷进去自己去体会总结。。。
能有小白一点的解释吗？？？？？
finally...
在油罐上搜索了好几个视频，总算有个讲的稍微清楚点的了。
===> 当你的程序中有大量重复、循环，DP帮你存储中间的一些计算结果，这样你不用每次都重新计算一遍。能将时间复杂度O(n)降低下来。
DP有三个steps:
Step1: Recursion
Step2: Memoize
这一步，由于储存了中间计算结果，时间复杂度降为O(2n+1).
Step3: Bottom-up
Code:
Resource from:
《What Is Dynamic Programming and How To Use It》
https://www.youtube.com/watch?v=vYquumk4nWw
