动态规划——收获

​ 动态规划第一篇

​ 之前说了最近要学习动态规划算法，然后自己也刷了十几道题目。下面说一下自己的看法。

​ 首先动态规划的效率确实比很多暴力解法要好很多。但是同时必须要付出空间上的开销。一般都是一个dp数组。从我做的题目来看，动态规划就是求解N处的某个问题的解f(n)的最优解。同时f(n)又与f(n-1),f(n-2)等有关。最重要的就是如何求解这些关系。暴力方法可以使用递归直接去求解，但是如果用树形图画出求解过程，就会发现有很多f(k)会被多次计算，这就是开销最大的地方。那么我们自然而然的想法就是减少f(k)的计算次数，怎么做？一种是带一个备忘录，这个方法也不是最优的。最优的是自底向上的来计算f(i)并且进行记录，这样可以减少子问题的计算次数，也就提升了计算效率。有时间再取一些例子进行分享。

​ 😪