I’ve repeatedly emphasized in dynamic programming that you learn recursion first, then memorization, and then dynamic programming.

The reason has been very clear, I believe you have understood. If you don’t understand, I strongly recommend reading the article first.

Although many friends who read my article know to learn mnemonic recursion first, some fans still ask me: “Mnemonic recursion is always wrong when it is converted into dynamic programming, what should I do if I can’t get to the point? Is there any point?”

Today I’m going to answer that question from my fans.

In fact, my article on dynamic programming gave you a general idea of how to convert memorization recursion into dynamic programming, but maybe not in great detail, so today we’re going to try to refine it.

Let’s start with the classic example of climbing stairs to give you the basics. Now, I’m going to take you through a more complicated problem.

Climb the stairs

Topic describes

A person who climbs stairs can only climb 1 or 2 steps at a time, assuming n steps, how many different ways can that person climb stairs?

Train of thought

Since the NTH step must come from the n-1 step or the N-2 step, the number of steps to the NTH step is the number of steps to the n-1 step plus the number of steps to the n-1 step.

Memorized recursive code:

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);
Copy the code

First of all, in order to see the relationship, we will change the name of the memo and change the memo to 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);
Copy the code

Nothing else has changed except the name.

So how can this memorized recursive code be transformed into a dynamic program? Here I’ve summarized three steps that make it easy to turn a lot of memorized recursion into a dynamic program.

1. Build dp array according to the input parameter of mnemonization recursion

In the topic of dynamic programming, Sifa also mentioned that the core of dynamic programming is state. The time complexity is the number of states, the space complexity is the number of states if you ignore the rolling array optimization, and what is the number of states? Isn’t it the Cartesian product of the range of states? And the state corresponds exactly to the entry of the mnemonized recursion.

So for this problem, obviously the state is the current step. So we have n states. So let’s just create a one-dimensional array of length N.

I use FROM to represent the memorized recursive code before transformation, and to represents the dynamic programming code after transformation. (The same as below, no further elaboration)

from:

dp = {};
function climbStairs(n) {}
Copy the code

to:

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

2. Populate the initial dp array with the return value of the memorized recursion leaf node

If n == 1 return 1 and if n == 2 return 2, which correspond to the leaf node of the recursion tree, the two lines of code will not be executed until they reach the leaf node. The result is then merged according to the return value of the child DP function, which is a typical back-order traversal.

If you transform it into iteration, how do you do that? The naive idea is to start with a leaf node and simulate the return of a recursive stack, and yes, that’s the nature of dynamic programming. It starts at the leaf node and ends at the root node, which is why memorization recursion is often called top-down and dynamic programming is called bottom-up. The bottom and top here can be viewed as the leaves and roots of a recursive tree.

We know the essential difference between mnemonic recursion and dynamic programming. Next, we populate the initialization, the logic of which is to memorize the return part of the recursion.

from:

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

to:

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

The length of dp is n, and the index range is [0,n-1], so dp[n-1] corresponds to dp(n) of memorization recursion. So dp[0] = 1 is equivalent to if n == 1 above: return 1. If you want the two to be exactly the same, you can change the array length to n + 1, and the array index 0 is not needed.

3. Enumerate cartesian products and copy master logic

  1. If (XXX in dp) return dp[XXX
  2. Put the recursive function f(XXX, YYy…) To dp [XXX] [yyy] […]. At the top of the stairs is dp[n].
  3. Change recursion to iteration. For example, in this problem, climbStairs(N-1) and climbStairs(n-2) are called recursion n times at climbStairs(N). What we need to do is iterative simulation. For example, if we call it n times, we’ll simulate execution n times with a layer of loop. If there are two parameters, there are two loops, three loops, and so on.

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;
}
Copy the code

to:

function climbStairs(n) {
  // ...
  // This loop is the Cartesian product of the states we mentioned above. Since this problem has only one state, enumerating one level is good. If there are two states, then the Cartesian product can be done with two cycles. For who circulates in the outer layer and who circulates in the inner layer, see my topic on dynamic programming.
  for (let i = 2; i < n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[dp.length - 1];
}
Copy the code

By combining the results of the above steps, we can transform the original memorization recursion into dynamic programming.

Complete code:

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];
}
Copy the code

Some people might think this is too easy. It’s actually a little bit easier. And I also admit that some mnemonic recursions are harder to rewrite, and when mnemonic recursions are easier to write, it’s more difficult to change to dynamic programming as I explained in dynamic programming for those of you who don’t know.

As far as I know, if dynamic programming can pass, most mnemonic recursions can pass. There are some extreme cases where mnemonization recursion fails: there are too many force-link test cases and too many test cases with large data volume. This is because the timeout judgment of force link is the sum of The Times of multiple test cases, rather than calculating the time separately.

Next, I’ll take a slightly more difficult example (one that requires dynamic programming, and memorization recursion times out). I’m going to walk you through the routine I gave you above.

Minimum number of side jumps

Topic describes

You are given a 3 runway road of length N, which contains a total of N + 1 points, numbered 0 through N. A frog starts from lane 2 at point 0 and wants to jump to point N. There may be some bumps in the road, however. You are given an array of obstacles of length n + 1, where obstacles[I] (range from 0 to 3) indicate that there is an obstacle in the path of obstacles[I] at point I. If [I] == 0, there is no obstacle at point I. There is no more than one obstacle in any of the three tracks at any one point. For example, if he is lazy [2] == 1, then there is an obstacle in track 1 at point 2. The frog jumps from point I to point I + 1 and the runway stays the same as long as there are no obstacles on the same runway at point I + 1. In order to avoid obstacles, the frog can also side jump to another runway at the same point (the two lanes may not be adjacent), but only if there are no obstacles at that point. For example, this frog can jump from runway 3 at point 3 to runway 1 at point 3. This frog starts from runway 2 at point 0 and wants to reach any runway at point n, please return to the minimum number of side jumps. Note: neither runway at point 0 nor point N will be obstructed. Example 1:Copy the code

Input: lazy = [0,1,2,3,0] output: 2 explanation: the optimal scheme is shown by the arrow in the figure above. There are two side jumps in total (red arrows). Note that the frog can only jump over obstacles if it jumps on its side (as shown at point 2 above). Example 2:Copy the code

Input: Obstacles = [0,1,1,3,3,0] Output: 0 Explanation: Runway 2 does not have any obstacles, so no side jumps are required. Example 3:Copy the code

Input: lazy = [0,2,1,0,3,0] output: 2 explanation: the optimal scheme is shown in the figure above. There are two side jumps. 1 <= n <= 5 \* 105 0 <= 1 In spite of obstacles[I] <= 3 in spite of obstacles[0] == [n] == 0Copy the code

Train of thought

The frog is jumping over and over again.

Explain the subject a little bit.

  • If there is no obstacle at the back of the runway, this is not better than a flat jump, we should be greedy to jump straight (not sideways). That’s because the worst we can do is go flat and then cross, which is the same thing as going sideways and then flat.

  • If there is an obstacle behind the current runway, we need to jump to an obstacle free lane with the counter + 1.

Finally, select the one with the least number of hops to reach the end point, which is the one with the smallest counter when reaching the leaf node in the corresponding recursion tree.

Use dp(pos, line) to indicate the minimum number of hops required to jump from POS to the end of the current channel line. It is not difficult to write the following mnemonized recursive code.

Since this article is mainly about memorization recursive transformation dynamic programming, so the details of this problem will not be introduced, we just look at the code.

Let’s look at the code:


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
            # Greedy flat jump
            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] :ifnxt ! = lineandobstacles[pos] ! = nxt: ans =min(ans, 1 +f(pos, nxt))
            dp[(pos, line)] = ans
            return ans

        return f(0.2)
Copy the code

This problem memorizes recursion over time and requires dynamic programming. So how do you transform TA into dynamic programming?

I’m going to use the same formula.

1. Build dp array according to the input parameter of mnemonization recursion

The above recursive function is dp(pos, line), and the state is the parameter. Therefore, it is necessary to build a two-dimensional array of M * n, where M and n are the size of the value range set of pos and line respectively. The value range of line is actually [1,3]. In order to facilitate index correspondence, this time siefa decided to waste a space. And since this is a minimization problem, it’s okay to initialize to infinity.

from:

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

        return f(0.2)
Copy the code

to:

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

2. Populate the initial dp array with the return value of the memorized recursion leaf node

So without further ado, let’s get right to the code.

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)
Copy the code

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])
Copy the code

3. Enumerate cartesian products and copy master logic

How does this problem enumerate states? Cartesian product of enumerated states, of course. Simple, just a few states and a few loops.

In the code.

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])
Copy the code

So what I’m going to do is just copy and paste the main logic of the mnemonic recursion.

from:

class Solution:
    def minSideJumps(self, obstacles: List[int]) - >int:
        dp = {}
        def f(pos, line) :
            #...
            # Greedy flat jump
            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] :ifnxt ! = lineandobstacles[pos] ! = nxt: ans =min(ans, 1 +f(pos, nxt))
            dp[(pos, line)] = ans
            return ans

        return f(0.2)
Copy the code

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 = pos + 1
                    dp[pos][line] = min(dp[pos][line], dp[pos - 1][line])
                else:
                    for nxt in range(1.4) :ifnxt ! = lineandobstacles[pos] ! = nxt: dp[pos][line] =min(dp[pos][line], 1 + dp[pos][nxt])

        return min(dp[-1])
Copy the code

So you can see that I’m basically copying the master logic and tweaking it a little bit. The basic reason for the change is:

  • It was a recursive function, so the return needs to be removed, like “continue”, so you can’t just let the function return, but continue enumerating the next state.
  • Dp [(pos, line)] = ans now fills our original 2d dp array.

You think this is the end of it?

You’d be wrong. I picked this one for a reason. The answer is wrong (WA).

Here’s what I want to tell you: since we use iteration to simulate recursion, we use a multi-layer loop to enumerate the Cartesian product of states, and the main logic part is the state transition equation, which is written in a way that depends on the order of the enumeration.

Dp [pos][line] only relies on dp[pos-1][line] and dp[pos][NXT].

The key of the problem is that NXT, for example, dp[2][1] is processed, d[2][1] depends on the value of DP [2][3], but actually DP [2][3] is not processed.

So the line of dynamically programmed code above has a problem:

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

It is possible that dp[pos][NXT] has not been evaluated when iterating through dp[pos][line], which is a bug.

So why is memorizing recursion okay?

It’s really simple. The sub-problems in the recursive function are not well calculated. We start the calculation after arriving at the leaf node, and then return up after the calculation. In fact, the return process is similar to iteration.

For example, the recursion tree of f(0,2) might look something like this, where the dotted line might not be reachable.

When you recurse from f(0, 2) to f(0, 1) or f(0, 3), it doesn’t count, so it doesn’t matter, the code keeps going to the leaf node, and when you get to the leaf node and come back, all the children must have been calculated, and the process is very much like a normal iteration.

So if f(0,2) recurses to f(0,3), f(0,3) will recurse down to the leaves and then back up, and when it comes back to f(0,2) again, f(0,3) must have been calculated.

Figuratively speaking, f(0,2) is a leader who tells his subordinates that f(0,3), I want XXXX. I don’t care how to achieve it. If you have something, you can directly give it to me (memorization); if not, you can find a way to get it (recursion). Either way, you get it out and get it to me.

If you use iterative dynamic programming, it’s easy to just give it to me. The point is that it’s not easy to get a recursion without it, at least in a similar loop, right?

So how do you solve this problem?

It’s easy to just rely on the calculated states each time.

For this problem, although dp[pos][NXT] may not have been calculated, dp[pos-1][NXT] must have been calculated because dp[POS-1][NXT] was calculated in the last main loop.

Dp [pos-1][NXT] It’s going to be case by case, but for this problem, it works.

This is because the logic here is that if there is an obstacle in front of the current track, then we cannot come from the previous position of the current track, but can only choose to cross from the other two tracks.

I drew a schematic diagram. Where X represents the obstacle, O represents the current position, and the number represents the sequence of time, jumping 1 and then 2…

-XO
---
---
Copy the code

Here, the following two cases are actually equivalent:

Case 1 (i.e. Dp [pos][NXT] above) :

-X2
--1
---
Copy the code

Case 2 (i.e. Dp [POS-1][NXT] above) :

-X3
-12
---
Copy the code

You can see they’re the same thing. Don’t understand? Look and think.

In summary, we will have no problem changing dp[pos][NXT] to dp[POS-1][NXT]. You encounter other problems also take a similar approach to analyze a wave.

Complete code:

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 = pos + 1
                    dp[pos][line] = min(dp[pos][line], dp[pos - 1][line])
                else:
                    for nxt in range(1.4) :ifnxt ! = lineandobstacles[pos] ! = nxt: dp[pos][line] =min(dp[pos][line], 1 + dp[pos-1][nxt])

        return min(dp[-1])
Copy the code

Strike while the iron is hot

Here’s another example, 1866. There are exactly K sticks that can be seen as permutations.

Train of thought

Memorizing recursive code directly:

class Solution:
    def rearrangeSticks(self, n: int, k: int) - >int:
        @lru_cache(None)
        def dp(i, j) :
            if i == 0 andj ! =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)
Copy the code

I don’t care what the problem is, where the code came from. So let’s say I’ve already written this code. So how do you transform it into dynamic programming? Continue with the trilogy.

1. Build dp array according to the input parameter of mnemonization recursion

Since there are n + 1 values of I [0-n] and k + 1 values of j [0-k]. So just initialize a two-dimensional array.

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

2. Populate the initial dp array with the return value of the memorized recursion leaf node

I == 0 and j == 0 is 1, so I write dp[0][0] = 1.

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

3. Enumerate cartesian products and copy master logic

It’s just a two-level loop enumeration of all combinations of I and 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]
Copy the code

Finally, I copied the master logic and we’re done.

For example, return XXX is changed to dp[parameter 1][parameter 2] = XXX.

The final code is:

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]
Copy the code

conclusion

Some mnemonic recursions are more difficult to rewrite, and when mnemonic recursions are easier to write, it’s more difficult to change to dynamic programming and I showed you in dynamic programming, if you don’t know.

I recommend starting with mnemonic recursion because in many cases mnemonic recursion is easy to write and fault tolerant (think frog jump above). This is because mnemonic recursion is always backward traversal, and will only go up when it reaches the leaf node. The upward calculation process is similar to iterative dynamic programming. Or you can think of iterative dynamic programming as simulating the process of memorizing recursion.

All we have to do is learn the easy ones, and then try to use mnemonic recursion for the hard ones. As far as I know, if dynamic programming can pass, most mnemonic recursions can pass. There is an extreme case where mnemonization recursion fails: there are too many force-link test cases, and there are too many test cases with large data. This is because the timeout judgment of force link is the sum of The Times of multiple test cases, rather than calculating the time separately.

To transform mnemonic recursion into dynamic programming, follow my three steps:

  1. Build the DP array from the input parameters of the mnemonized recursion
  2. Populate the initial dp array with the return values of the memorized recursion leaf nodes
  3. Enumerates the Cartesian product and copies the master logic

Another point to note is that the determination of the state transition equation is closely related to the direction of the enumeration, although the details vary greatly from topic to topic. But we just have to stick to one principle, and that is: never use uncomputed states, but only computed states.