可以这样理解吗？

其实是可以这么理解的，ADM的作者Skiena教授就是这么讲解DP的，因为但凡DP，一定有递推关系，否则递推关系都没有就更别说什么子问题重复计算了。刷表法的那个数组d，实际上就是预计算的状态函数，方框里的下标就是状态函数的参数，递归加memory和预计算刷表只是实现上的两种技巧，其本质是一样的，递归加memory更接近本质，刷表则是一种优化。

整个流程说白了就是

先想递归
发现重复计算
通过记忆化等方法弄掉重复计算
最后看下能不能通过利用计算顺序来做到去掉递归用「刷表」方式直接顺序计算，能搞定最好搞不定拉倒

实际上我按照这套mindset来考虑dp问题之后，会发现对于并不熟悉的dp题目，明显构思起来要比直接考虑「有什么状态？怎么扩展状态」这套顺手，因为递归是很自然的一种思维方式。当然，已经比较熟练直接就能看出来状态和转移方程的题目，以及一些状态实在太显眼比考虑递归还简单的题目，就不需要用这套了。

PS：有一些优化，使用记忆化搜索方式实现DP做不了，有的题目会被这个卡死，比如必须用滚动数组等方式压缩状态否则MLE的那种。有一些优化，使用刷表法做不了，比如实际访问的状态很稀疏又不能整齐控制顺序，你一建表就MLE或者TLE那种。所以两种DP主流实现方式都要掌握。

首先，"递归" 不是一种演算法，而是一种编程写法。

理论上讲，任何递归写法的程序都可以改为for循环实现。

"动态规划的本质"，我的理解是："利用已解决问题的答案去解决新问题"的思想方式。

这就需要记忆答案（可能不止一个问题的答案），在这些答案的基础上再走一小步，就解决了新问题。把新问题的答案记录下来，后续问题就可以直接利用而无需重新计算。这往往可以将指数级时间复杂度降低为多项式级。

如果问你 1+2+3+...+100=？

如果不是背过答案，能一口说出吗？

但是如果告诉你 1+2+3+...+99 的答案，就等于 4950。（这就是已解决问题的答案）

那么1+2+3+...+99+100=？你很容易就算出是5050。（这就是利用已解决问题的答案去解决新问题）

你比高斯算得还快，是因为不需要重新计算 1+2+3+...+99 的值，而是直接拿4950再加100即可。

那么是如何知道1+2+3+...+99=4950的呢？

因为1+2+3+...+98=4851是已知的，记住答案再加99即可，而不需要自己先从1加到98。

那么这个4851又是怎么知道的呢？

依次向前推，最后就变成了：

1+2=? 是3

因为 1=1。

试试把100换成n，用这个思路写出来就是递归。

这个思路反过来想就是for循环。

另一个回答中写道：

求一个数组的最小值，你遍历一遍，遍历到下标i的时候，是不是拿到的是当前最优解，也勉强称之为dp。

这就说到dp的本质，dp是一种解决问题的思想方式。

只要用一个变数记录当前最小值，当遍历到下标 i 的时候，我只需要利用当前最小值与第 i 个元素进行比较，而不用将第 i 个元素与前面所有元素重新比较一遍。从这个角度想，它是dp。代码写出来可以是一个简单的for循环，也可以是一个递归，这与dp无关。

个人理解，望指正。

个人认为不是，本质应该是状态的转移与优化，递归只是程序中某个函数本身调用自己，是一种特殊的程序过程，只是可能某些情况可以用递归演算法写出来而已。跟用数组迭代写出来一样的道理。而动态规划本质并不是程序的过程，是一个具体的演算法，用过程描述本质有点不妥，具体可以了解动态规划在运筹学上的解释。

递归+记忆化确实是解决部分动态规划问题的有效手段。

但是，需要明白一点，不是每一种动态规划都可以很方便的用上述方法实现的。

动态规划的本质应该是在高维的决策空间中按照其拓扑序进行迭代然后求得最优解的演算法。

而递归+记忆化很大程度上只是为了避免一些重复的计算。

再者，递归演算法还需考虑栈空间的问题。

综上，动态规划的本质不是递归+记忆化。

还有树形dp，更多奇形怪状的动态规划，你所说的就是用个vis数组记录一个fun(x)的结果，省的多次计算，实际上这种的dp和线段树有啥区别吗，勉强称之为dp。

这样说吧，让你求一个数组的最小值，你遍历一遍，遍历到下标i的时候，是不是拿到得是当前最优解，也勉强称之为dp

我觉得大概可以这么理解吧。

动态规划问题的特点就是有最优子结构性质，然后最小的子问题解会一直复用。

所以最优子结构就用递归做咯（不过递归的问题一般可能会有不用递归的快速解法），最小问题的解就记忆下来复用咯。

不过动态规划是一种问题类型，递归是一类解题方法，这么说其实感觉不是特别对味。

我这里写了一篇自己总结动态规划，而且有pdf可供下载

内容由于详细，所以有点多，在回答界面会有格式会乱掉

我把链接放在这里，直接跳转就可以看到

Johngo：动态规划一篇就够了 全网第二详细, 逐步理解, 万字总结?

zhuanlan.zhihu.com图标

下面是上述链接的目录，双手奉上

0. 首先，先大致列下这篇文章会讲到什么

1.相较于暴力解法，动态规划带给我们的是什么？为什么会有重叠子问题以及怎么去避免的?2.用不同难度的动态规划问题举例说明， 最后会使用《打家劫舍》系列三个题再重温一次.一、动态规划带给我们的优势传统递归 vs. DP1. 先 递归解决2. 后 动态规划解决3. 动态规划 + 优化二、动态规划四大解题步骤处理问题案例一：打家劫舍I 「来自leetcode198」

案例二：不同路径「来自leetcode62」

案例三：不同路径II 「来自leetcode63」案例四：打家劫舍II 「来自leetcode213」案例五：打家劫舍III 「来自leetcode337」

所有内容都可以进行完全下载下来成PDF版本

错了。

动态规划的本质是递推。

递推可以写成搜索的形式，搜索在程序中的实现体现为递归。

然而写成搜索的形式后会导致复杂度崩溃，于是加上记忆化使之与朴素递推复杂度相同。

不是呀，递归+记忆化只是一种实现dp的方式，但很多动态规划问题不一定就是递归的。。。。

推荐阅读：
相关文章