关于leetcode:读者西法记忆化递归究竟怎么改成动态规划啊

title:
tags: [算法, 动静布局]
date: 2021-05-18
categories:

• [动静布局]

我在动静布局专题反复强调了 先学习递归，再学习记忆化，最初再学动静布局。

其中起因曾经讲得很透了，置信大家曾经明确了。如果不明确，强烈建议先看看那篇文章。

只管很多看了我文章的小伙伴晓得了先去学记忆化递归，然而还是有一些粉丝问我：“记忆化递归转化为动静布局老是出错，不得要领怎么办？有没有什么要领呀？”

明天我就来答复一下粉丝的这个问题。

实际上我的动静布局那篇文章曾经讲了将记忆化递归转化为动静布局的大略的思路，只是可能不是特地细，明天咱们就尝试 细化一波。

咱们依然先以经典的爬楼梯为例，给大家讲一点基础知识。接下来，我会带大家解决一个更加简单的题目。

<!– more –>

爬楼梯

题目形容

一个人爬楼梯，每次只能爬 1 个或 2 个台阶，假如有 n 个台阶，那么这个人有多少种不同的爬楼梯办法？

思路

因为 第 n 级台阶肯定是从 n – 1 级台阶或者 n – 2 级台阶来的 ，因而到第 n 级台阶的数目就是 到第 n - 1 级台阶的数目加上到第 n - 1 级台阶的数目。

记忆化递归代码：

const memo = {};
function climbStairs(n) {if (n === 1) return 1;
  if (n === 2) return 2;
  if (n in memo) return memo[n];
  ans = climbStairs(n - 1) + climbStairs(n - 2);
  memo[n] = ans;
  return ans;
}

climbStairs(10);

首先为了不便看出关系，咱们先将 memo 的名字改一下，将 memo 换成 dp：

const dp = {};
function climbStairs(n) {if (n === 1) return 1;
  if (n === 2) return 2;
  if (n in dp) return dp[n];
  ans = climbStairs(n - 1) + climbStairs(n - 2);
  dp[n] = ans;
  return ans;
}

climbStairs(10);

其余中央一点没动，就是名字改了下。

那么这个记忆化递归代码如何革新成动静布局呢？这里我总结了三个步骤，依据这三个步骤就能够将 很多 记忆化递归轻松地转化为动静布局。

1. 依据记忆化递归的入参建设 dp 数组

在动静布局专题中，西法还提过 动静布局的外围就是状态。动静布局问题工夫复杂度打底就是状态数，空间复杂度如果不思考滚动数组优化打底也是状态数 ，而状态数是什么？不就是各个状态的取值范畴的笛卡尔积么？而 状态正好对应的就是记忆化递归的入参。

对应这道题，显然状态是以后位于第几级台阶。那么状态数就有 n 个。因而开拓一个长度为 n 的一维数组就好了。

我用 from 示意革新前的记忆化递归代码，to 示意革新后的动静布局代码。（下同，不再赘述）

from:

dp = {};
function climbStairs(n) {}

to:

function climbStairs(n) {const dp = new Array(n);
}

2. 用记忆化递归的叶子节点返回值填充 dp 数组初始值

如果你模仿下面 dp 函数的执行过程会发现: if n == 1 return 1 和 if n == 2 return 2，对应递归树的叶子节点，这两行代码 深刻到叶子节点才会执行 。接下来再依据子 dp 函数的返回值合并后果，是一个典型的 后序遍历。

如果革新成迭代，如何做呢？一个奢侈的想法就是从叶子节点开始模仿递归栈返回的过程，没错 动静布局实质就是如此 。从叶子节点开始，到根节点完结， 这也是为什么记忆化递归通常被称为自顶向下，而动静布局被称为自底向上的起因。这里的底和顶能够看做是递归树的叶子和根。

晓得了记忆化递归和动静布局的本质区别。接下来，咱们填充初始化，填充的逻辑就是记忆化递归的叶子节点 return 局部。

from:

const dp = {};
function climbStairs(n) {if (n == 1) return 1;
  if (n == 2) return 2;
}

to:

function climbStairs(n) {const dp = new Array(n);
  dp[0] = 1;
  dp[1] = 2;
}

dp 长度为 n，索引范畴是 [0,n-1]，因而 dp[n-1] 对应记忆化递归的 dp(n)。因而 dp[0] = 1 等价于下面的 if n == 1: return 1。如果你想让二者齐全对应也是能够的，数组长度开拓为 n + 1，并且数组索引 0 不必即可。

3. 枚举笛卡尔积，并复制主逻辑

1. if (xxx in dp) return dp[xxx] 这种代码删掉
2. 将递归函数 f(xxx, yyy, …) 改成 dpxxx[….]，对应这道题就是 climbStairs(n) 改成 dp[n]
3. 将递归改成迭代。比方这道题每次 climbStairs(n) 递归调用了 climbStairs(n-1) 和 climbStairs(n-2)，一共调用 n 次，咱们要做的就是迭代模仿。比方这里调用了 n 次，咱们就用一层循环来模仿执行 n 次。如果有两个参数就两层循环，三个参数就三层循环，以此类推。

from:

const dp = {};
function climbStairs(n) {
  // ...
  if (n in dp) return dp[n];
  ans = climbStairs(n - 1) + climbStairs(n - 2);
  dp[n] = ans;
  return ans;
}

to:

function climbStairs(n) {
  // ...
  // 这个循环其实就是咱下面提到的状态的笛卡尔积。因为这道题就一个状态，枚举一层就好了。如果状态有两个，那么笛卡尔积就能够用两层循环搞定。至于谁在外层循环谁在内层循环，请看我的动静布局专题。for (let i = 2; i < n; i++) {dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[dp.length - 1];
}

将下面几个步骤的成绩合并起来就能够将原有的记忆化递归革新为动静布局了。

残缺代码：

function climbStairs(n) {if (n == 1) return 1;
  const dp = new Array(n);
  dp[0] = 1;
  dp[1] = 2;

  for (let i = 2; i < n; i++) {dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[dp.length - 1];
}

有的人可能感觉这道题太简略了。实际上的确有点简略了。而且我也抵赖 有的记忆化递归比拟难以改写，什么状况记忆化递归比拟好写，改成动静布局就比拟麻烦我也在动静布局专题给大家讲过了，不分明的同学翻翻。

据我所知，如果动静布局能够过，大多数 记忆化递归都能够过。有一些极其状况记忆化递归过不了：那就是力扣测试用例偏多，并且数据量大的测试用例比拟多。这是因为力扣的超时判断是多个测试用例的用时总和，而不是独自计算工夫。

接下来，我再举一个略微难一点的例子（这个例子就必须应用动静布局能力过，记忆化递归会超时）。带大家相熟我下面给大家的套路。

1824. 起码侧跳次数

题目形容

给你一个长度为  n  的  3 跑道路线，它总共蕴含  n + 1  个   点，编号为  0  到  n。一只青蛙从  0  号点第二条跑道   登程，它想要跳到点  n  处。然而路线上可能有一些阻碍。给你一个长度为 n + 1  的数组  obstacles，其中  obstacles[i]（取值范畴从 0 到 3）示意在点 i  处的  obstacles[i]  跑道上有一个阻碍。如果  obstacles[i] == 0，那么点  i  处没有阻碍。任何一个点的三条跑道中   最多有一个   阻碍。比方说，如果  obstacles[2] == 1，那么阐明在点 2 处跑道 1 有阻碍。这只青蛙从点 i  跳到点 i + 1  且跑道不变的前提是点 i + 1  的同一跑道上没有阻碍。为了规避阻碍，这只青蛙也能够在   同一个   点处   侧跳   到 另外一条   跑道（这两条跑道能够不相邻），但前提是跳过去的跑道该点处没有阻碍。比方说，这只青蛙能够从点 3 处的跑道 3 跳到点 3 处的跑道 1。这只青蛙从点 0 处跑道 2  登程，并想达到点 n  处的 任一跑道，请你返回 起码侧跳次数。留神：点 0  处和点 n  处的任一跑道都不会有阻碍。示例 1：

输出：obstacles = [0,1,2,3,0]
输入：2
解释：最优计划如上图箭头所示。总共有 2 次侧跳（红色箭头）。留神，这只青蛙只有当侧跳时才能够跳过阻碍（如上图点 2 处所示）。示例 2：

输出：obstacles = [0,1,1,3,3,0]
输入：0
解释：跑道 2 没有任何阻碍，所以不须要任何侧跳。示例 3：

输出：obstacles = [0,2,1,0,3,0]
输入：2
解释：最优计划如上图所示。总共有 2 次侧跳。提醒：obstacles.length == n + 1
1 <= n <= 5 \* 105
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0

思路

这个青蛙在重复横跳？？

略微解释一下这个题目。

• 如果以后跑道前面一个地位没有障碍物，这种状况左右横跳肯定不会比间接平跳更优，咱们应该贪婪地间接平跳（不是横跳）过来。这是因为最坏状况咱们能够 先平跳过去再横跳，这和先横跳再平跳是一样的。
• 如果以后跑道前面一个地位有障碍物，咱们须要横跳到一个没有障碍物的通道，同时横跳计数器 + 1。

最初选取所有达到起点的横跳次数起码的即可，对应递归树中就是达到叶子节点时计数器最小的。

应用 dp(pos, line) 示意以后在通道 line，从 pos 跳到起点 须要的起码的横跳数。不难写出如下记忆化递归代码。

因为本篇文章次要讲的是记忆化递归革新动静布局，因而这道题的细节就不多介绍了，大家看代码就好。

咱们来看下代码：

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = {}
        def f(pos, line):
            if (pos, line) in dp: return dp[(pos, line)]
            if pos == len(obstacles) - 1:
                return 0
            # 贪婪地平跳
            if obstacles[pos + 1] != line:
                ans = f(pos + 1, line)
                dp[(pos, line)] = ans
                return ans
            ans = float("inf")
            for nxt in [1, 2, 3]:
                if nxt != line and obstacles[pos] != nxt:
                    ans = min(ans, 1 +f(pos, nxt))
            dp[(pos, line)] = ans
            return ans

        return f(0, 2)

这道题记忆化递归会超时，须要应用动静布局才行。那么如何将 ta 革新成动静布局呢？

还是用下面的口诀。

1. 依据记忆化递归的入参建设 dp 数组

下面递归函数的是 dp(pos, line)，状态就是形参，因而须要建设一个 m * n 的二维数组，其中 m 和 n 别离是 pos 和 line 的取值范畴汇合的大小。而 line 取值范畴其实就是 [1,3]，为了不便索引对应，这次西法决定节约一个空间。因为这道题是求最小，因而初始化为无穷大没故障。

from:

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = {}
        def f(pos, line):
            # ...

        return f(0, 2)

to:

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = [[float("inf")] * 4 for _ in range(len(obstacles))]
        # ...
        return min(dp[-1])

2. 用记忆化递归的叶子节点返回值填充 dp 数组初始值

不多说了，间接上代码。

from:

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = {}
        def f(pos, line):
            if pos == len(obstacles) - 1:
                return 0
            # ...

        return f(0, 2)

to:

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = [[float("inf")] * 4 for _ in range(len(obstacles))]
        dp[0] = [0, 1, 0, 1]
        # ...
        return min(dp[-1])

3. 枚举笛卡尔积，并复制主逻辑

这道题如何枚举状态？当然是枚举状态的笛卡尔积了。简略，几个状态就几层循环呗。

上代码。

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = [[float("inf")] * 4 for _ in range(len(obstacles))]
        dp[0] = [0, 1, 0, 1]
        for pos in range(1, len(obstacles)):
            for line in range(1, 4):
                # ...
        return min(dp[-1])

接下来就是把记忆化递归的主逻辑复制一下粘贴过去就行。

from:

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = {}
        def f(pos, line):
            # ...
            # 贪婪地平跳
            if obstacles[pos + 1] != line:
                ans = f(pos + 1, line)
                dp[(pos, line)] = ans
                return ans
            ans = float("inf")
            for nxt in [1, 2, 3]:
                if nxt != line and obstacles[pos] != nxt:
                    ans = min(ans, 1 +f(pos, nxt))
            dp[(pos, line)] = ans
            return ans

        return f(0, 2)

to：

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = [[float("inf")] * 4 for _ in range(len(obstacles))]
        dp[0] = [0, 1, 0, 1]
        for pos in range(1, len(obstacles)):
            for line in range(1, 4):
                if obstacles[pos - 1] != line: # 因为自底向上，因而是和 pos - 1 建立联系，而不是 pos + 1
                    dp[pos][line] = min(dp[pos][line], dp[pos - 1][line])
                else:
                    for nxt in range(1, 4):
                        if nxt != line and obstacles[pos] != nxt:
                            dp[pos][line] = min(dp[pos][line], 1 + dp[pos][nxt])

        return min(dp[-1])

能够看出我根本就是把主逻辑复制过去，略微改改。改的根本就是因为：

• 之前是递归函数，因而 return 须要去掉，比方改成 continue 啥的，不能让函数间接返回，而是持续枚举下一个状态。
• 之前是 dp[(pos, line)] = ans 当初则改成填充咱下面初始好的二维 dp 数组。

你认为这就完结了么？

那你就错了。之所以选这道题是有起因的。这道题间接提交会报错，是答案谬误（WA）。

这里我要通知大家的是：因为咱们应用迭代模仿递归过程，应用多层循环枚举状态的笛卡尔积，而主逻辑局部则是状态转移方程，而转移方程的书写和枚举的程序非亲非故。

从代码不难看出：对这道题来说咱们采纳的是从小到大枚举，而 dppos 也仅仅依赖 dppos-1 和 dppos。

而问题的要害是 nxt，比方解决到了 dp2，d2 依赖了 dp2 的值，而实际上 dp2 是没有解决到的。

因而下面动静布局的的这一行代码有问题：

dp[pos][line] = min(dp[pos][line], 1 + dp[pos][nxt])

因为 遍历到 dppos 的时候，有可能 dppos 还没计算好(没有枚举到)，这就是产生了 bug。

那为什么记忆化递归就没问题呢？

其实很简略。递归函数外面的子问题 都是没有计算好的 ，到叶子节点后再开始计算，计算好后往上返回，而 返回的过程其实和迭代是相似的。

比方这道题的 f(0,2) 的递归树大略是这样的，其中虚线标识可能无奈达到。

当从 f(0, 2) 递归到 f(0, 1) 或者 f(0, 3) 的的时候，都是没计算好的，因而都无所谓，代码会 持续往叶子节点方向扩大，达到叶子节点返回后，所有的子节点必定都曾经计算好了，接下来的过程和一般的迭代就很像了。

比方 f(0,2) 递归到 f(0,3)，f(0,3) 会持续向下递归晓得叶子节点，而后向上返回，当再次回到 f(0,2) 的时候，f(0,3) 肯定是曾经计算好的。

形象点来说就是：f(0,2) 是一个 leader，通知他的上司 f(0,3)，我想要 xxxx，怎么实现我不论，你有的话间接给我（记忆化），没有的话想方法获取（递归）。不论怎么样，反正你给我弄出来送到我手上。

而如果应用迭代的动静布局，你有的话间接给我（记忆化）很容易做到。要害是没有的话想方法获取（递归）不容易做到啊，至多须要一个相似的循环去实现吧？

那如何解决这个问题呢？

很简略，每次 只依赖曾经计算好的状态 就好了。

对于这道题来说，尽管 dppos 可能没计算好了，那么 dppos-1 肯定是计算好的，因为 dppos-1 曾经在上一次主循环计算好了。

然而间接改成 dppos-1 逻辑还对么？这就要具体问题具体分析了，对于这道题来说，这么写是能够的。

这是因为这里的逻辑是 如果以后赛道的后面一个地位有障碍物，那么咱们不能从以后赛道的前一个地位过去，而只能抉择从其余两个赛道横跳过来。

我画了一个简图。其中 X 示意障碍物，O 示意以后的地位，数字示意工夫上的先后循序，先跳 1 再跳 2。。。

-XO
---
---

在这里，而以下两种状况其实是等价的：

状况 1（也就是下面 dppos 的状况）：

-X2
--1
---

状况 2（也就是下面 dppos-1 的状况）：

-X3
-12
---

能够看出二者是一样的。没懂？多看看，多想想。

综上，咱们将 dppos 改成 dppos-1 不会有问题。大家遇到其余问题也采取相似思路剖析一波即可。

残缺代码：

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        dp = [[float("inf")] * 4 for _ in range(len(obstacles))]
        dp[0] = [0, 1, 0, 1]
        for pos in range(1, len(obstacles)):
            for line in range(1, 4):
                if obstacles[pos - 1] != line: # 因为自底向上，因而是和 pos - 1 建立联系，而不是 pos + 1
                    dp[pos][line] = min(dp[pos][line], dp[pos - 1][line])
                else:
                    for nxt in range(1, 4):
                        if nxt != line and obstacles[pos] != nxt:
                            dp[pos][line] = min(dp[pos][line], 1 + dp[pos-1][nxt])

        return min(dp[-1])

趁热打铁再来一个

再来一个例子，1866. 恰有 K 根木棍能够看到的排列数目。

思路

间接上记忆化递归代码：

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        @lru_cache(None)
        def dp(i, j):
            if i == 0 and j != 0: return 0
            if i == 0 and j == 0: return 1
            return (dp(i - 1, j - 1) + dp(i - 1, j) * (i - 1)) % (10**9 + 7)
        return dp(n, k) % (10**9 + 7)

咱不论这个题是啥，代码怎么来的。假如这个代码咱曾经写进去了。那么如何革新成动静布局呢？持续套用三部曲。

1. 依据记忆化递归的入参建设 dp 数组

因为 i 的取值 [0-n] 一共 n + 1 个，j 的取值是 [0-k] 一共 k + 1 个。因而初始化一个二维数组即可。

dp = [[0] * (k+1) for _ in range(n+1)]

2. 用记忆化递归的叶子节点返回值填充 dp 数组初始值

因为 i == 0 and j == 0 是 1，因而间接写 dp0 = 1 就好了。

dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1

3. 枚举笛卡尔积，并复制主逻辑

就是两层循环枚举 i 和 j 的所有组合就好了。

dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(1, n + 1):
    for j in range(1, min(k, i) + 1):
        # ...
return dp[-1][-1]

最初把主逻辑复制过去竣工了。

比方：return xxx 改成 dp 形参一 = xxx 等小细节。

最终的一个代码就是：

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        dp = [[0] * (k+1) for _ in range(n+1)]
        dp[0][0] = 1

        for i in range(1, n + 1):
            for j in range(1, min(k, i) + 1):
                dp[i][j] = dp[i-1][j-1]
                if i - 1 >= j:
                    dp[i][j] += dp[i-1][j] * (i - 1)
                dp[i][j] %= 10**9 + 7
        return dp[-1][-1]

总结

有的记忆化递归比拟难以改写，什么状况记忆化递归比拟好写，改成动静布局就比拟麻烦我也在动静布局专题给大家讲过了，不分明的同学翻翻。

我之所以举荐大家从记忆化递归动手，正是因为很多状况下记忆化写起来简略，而且容错高（想想下面的青蛙跳的例子）。这是因为记忆化递归总是后序遍历，会在达到叶子节点只会往上计算。而往上计算的过程和迭代的动静布局是相似的。或者你也能够认为迭代的动静布局是在模仿记忆化递归的 归的过程。

咱们要做的就是把一些容易革新的办法学会，接下来面对难的尽量用记忆化递归。据我所知，如果动静布局能够过，大多数记忆化递归都能够过。有一个极其状况记忆化递归过不了：那就是力扣测试用例偏多，并且数据量大的测试用例比拟多。这是因为力扣的超时判断是多个测试用例的用时总和，而不是独自计算工夫。

将记忆化递归革新成动静布局能够参考我的这三个步骤：

1. 依据记忆化递归的入参建设 dp 数组
2. 用记忆化递归的叶子节点返回值填充 dp 数组初始值
3. 枚举笛卡尔积，并复制主逻辑

另外有一点须要留神的是：状态转移方程的确定和枚举的方向非亲非故，尽管不同题目细节差别很大。然而咱们只有牢牢把握一个准则就行了，那就是：永远不要用没有计算好的状态，而是仅实用曾经计算好的状态。