如何思考递归

参考：动态规划入门：从记忆化搜索到递推【基础算法精讲 17】

1. 确定入口和边界

  • 入口应该选最大的，因为递归自顶向下，而递推自底向上。
  • 边界的选取应该保证会返回一个确定的答案，并且不能再继续下去。

2. 确定状态转移方程式

  • 大问题分解成子问题，并且都可以用同一种方法解决。

3. 递归 + 保存状态 = 记忆化搜索

  • memo 数组大小是状态最大值 + 1。

如何翻译成递推

递推翻译图示

1. 如何确定 f 数组个数：

  • 递归范围最大值带入到 f 的表达式中，得到的最大值 + 1。

2. 如何确定数组初始值：

  • f[递归边界 + 偏移量] = dfs(边界)。

3. 如何循环：

  • 倒着来。

4. for 循环起始和终止如何确定？

  • 起始为递归边界 + 偏移量。
  • 终止不能超出递归范围。

空间优化

  • 比如把二维压缩成一维，我们只需要关注压缩掉的那一维的状态是怎么转移的。依赖哪几个状态，有没有被覆盖，从而引入变量来表示和区分。
  • 对于数组下标越界，我们可以通过 if-else 解决。