例如背包问题，通常我们使用一个 dp[i][j] 数组记录子问题的解，依次从小到大求解所有子问题。使用记忆化递归也可以完成这类工作（例如定义一个 dp(i,j)函数），这样做只需求解必要的少数几个子问题即可得到题目的解，不用求解所有子问题。这看似比传统的递推做法还快。那为什么人们常用递推而不用记忆化递归？

  1. 不同的题目用不同的写法比较方便；
  2. 记忆化有时候空间复杂度更高。

关于背包，递推可以滚动数组优化，递归就不行。

首先

这两种写法的时间复杂度是一样的

其次

这两种写法都很常用，只是对于许多特定的问题

用递推会减少代码长度而且看著更优美

递归的写法

您可以来看看【P3953】逛公园 - 洛谷

递归形式相对于递推形式有以下几个优点：

  1. 更直观，一旦写出状态转移方程，递归形式就相当于「模拟题」了。
  2. 在某些情况下，递归能少访问一些子问题。
  3. 拓扑序列不明，即很难找到子问题之间的执行先后顺序，比如一个乱七八糟的递归函数。

其中，1. 存在于所有 dp 题中，但 2. 和 3. 极少出现。

而递推形式有如下优点：

  1. 省时间省空间。减少子程序的调用，降低时间函数中的常数。
  2. 程序短一些
  3. 提供更广阔的优化空间。有时可以覆盖数据，从而大大降低空间复杂度（不只是优化常数）。

题主提到了 01背包，这可以说是3.的体现。其实图论中的 floyd 演算法 也是把数据覆盖减小到 [公式] 的空间复杂度的。

详细解释：

因为[公式]的两个子问题都是[公式]，故只要已知数组[公式]，就能得到数组 [公式]，所以只需保留至多 2 个数组即可，即空间复杂度优化为 [公式] 。

想起 noip2017，我没想到覆盖，直接用了递归形式，导致 d1t3 只AC了 1 个点，剩下 5 个MLE，还有 4 个 RE

其实我以前也有答过一些动规方面的问题：

递归问题是否都可以用动态规划求解？?

www.zhihu.com图标有什么问题是动态规划解不了的？?

www.zhihu.com图标

其实都可以，复杂度是一样的。

具体还是因题目而异，在不同的问题中一般会使用不同的写法，比如图上的问题使用记忆化搜索就方便得多。在正常循环遍历的顺序已经满足要求时递推便更加方便。

推荐阅读：
相关文章