动态规划
最近在做题的时候遇到了递归,隐约感觉与动规有点相似,但自已又说不清楚,于是找了很多文章,这里摘录一片最基础但也是最清楚的文章,原文链接是这个。
原理
动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等。
既然是要求最值,核心问题是什么呢?求解动态规划的核心问题是穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值呗。
动态规划就这么简单,就是穷举就完事了?我看到的动态规划问题都很难啊!
首先,动态规划的穷举有点特别,因为这类问题存在「重叠子问题」,如果暴力穷举的话效率会极其低下,所以需要「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算。