Recursion and Dynamic programming¶

:::tip Info The key to solving a DP problem efficiently is finding a way to break the problem into subproblems such that

the original problem can be solved relatively easily once solutions to the subproblems are available, and
these subproblem solutions are cached

Like divide-and-conquer, DP solves the problem by combining the solutions of multiple smaller problems, but what makes DP different is that the same subproblem may reoccur. Therefore, a key to making DP efficient is caching the results of intermediate computations. :::

:::tip Although conceptually DP involves recursion, often for efficiency the cache is built “bottomup”, i.e., iteratively. (Example: Number of ways Problem)

When DP is implemented recursively the cache is typically a dynamic data structure such as a hash table or a BST; when it is implemented iteratively the cache is usually a one- or multi-dimensional array.

To save space, cache space may be recycled once it is known that a set of entries will not be looked up again.

A common mistake in solving DP problems is trying to think of the recursive case by splitting the problem into two equal halves, a la quicksort, i.e., solve the subproblems for subarrays A[0; bn2 c] and A[bn2 c + 1; n] and combine the results. However, in most cases, these two subproblems are not sufficient to solve the original problem. :::

Dynamic programming can be understood as recursive (Memoization) of look-up tables. So what is recursion? What is a look-up table (Memoization)?

Recursion¶

Recursion refers to the method of using the function itself in the definition of a function.

The use of recursion in the algorithm can easily complete some functions implemented with loops, such as traversing a binary tree first, middle, and later. Recursion is widely used in algorithms, including functional programming, which is becoming increasingly popular.

A meaningful recursive algorithm will decompose the problem into similar sub-problems with a reduced scale. When the sub-problem is reduced to an ordinary one, its solution can be known. Then establish the connection between the recursive functions to solve the original problem, which is the meaning of our use of recursion. To be precise, recursion is not an algorithm, it is a programming method corresponding to iteration. However, because of the implicit use of the function call stack, it is easier to write recursively.

To solve a problem using recursion, there must be a recursive termination condition (the infiniteness of the algorithm). Although the following code is also recursive, it is not an effective algorithm because it cannot end:

def f(n):
  return n + f(n-1)

More cases should be:

def f(n):
  if n == 1: return 1
  return n + f(n-1)

Practice recursion¶

A simple way to practice recursion is to change all the iterations you write into recursive form. For example, if you write a program whose function is "output a string in reverse order", it is very easy to write it out using iteration, so can you use recursion to write it out? Through such exercises, you can gradually adapt to using recursion to write programs.

If you are already familiar with recursion, then we continue to look down.

Repeated calculation in recursion¶

There may be so many repeated calculations in recursion. In order to eliminate such repeated calculations, a simple way is to memoize recursion. That is, while recursively, use the "record table" (such as a hash table or an array) to record the situation we have calculated. When the next time we encounter it, if it has been calculated before, then just return directly, so as to avoid duplication Calculation. In fact, in dynamic programming, the DP array has the same function as the "record table" here.

Summary¶

The advantage of using recursive functions is that the logic is simple and clear, but the disadvantage is that too deep calls will cause stack overflow. Here I have listed several algorithmic questions, these algorithmic questions can be easily written using recursion:

Recursively implement sum
Binary tree traversal
Stairway problem
Tower of Hanoi problem
Yanghui Triangle

When you have adapted to recursion, let us continue to learn dynamic programming!

Dynamic planning¶

If you are already familiar with the technique of recursion, using recursion to solve problems is very intuitive, and the code is relatively simple to write. At this time, let’s focus on another issue - double-calculation. Through analysis (you can try to draw a recursive tree), we can see that recursion can reduce the size of the problem while is it possible to double-calculation. In 279. Perfect Squares I solve this problem by recursive method, and at the same time maintain a cache internally to store the calculated calculations, which can reduce a lot of Operation. This is actually similar to dynamic programming.

::: 💡 Tip: If you find that there is no double calculation, there is no need to use memoized recursion or dynamic programming. :::

Therefore, dynamic programming is to enumerate all possibilities. However, compared to brute force enumeration, dynamic programming will not have double counting. Therefore, how to ensure that the enumeration is not repeated is one of the key points. Since recursion uses a function call stack to store data, it is easy to burst when the stack becomes very large.

Explosion stack¶

Let's explain it in conjunction with the problem of summation. Given an array, find the sum of all items in the array and require the use of recursion.

Code:

function sum(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  return nums[0] + sum(nums.slice(1));
}

Let's take a look at it intuitively with a recursion tree.

dynamic-programming-1

There is no problem with this approach, but every time a function is executed, there is a certain overhead. Take the JS engine to execute JS, every time the function is executed, the stack operation will be carried out, and the preprocessing and execution process will be carried out, so the memory allocation will be big When the amount of data is large, it is easy to cause the stack to burst.

The JS engine in the browser has a limit on the length of the code execution stack, if it exceeds, the stack will burst and an exception will be thrown.

Repeated calculation¶

Let's give another example of repeated calculations, problem description:

A person climbing stairs can only climb 1 or 2 steps at a time. Assuming there are n steps, how many different ways does this person have to climb stairs?

746. Min Cost Climbing Stairs is a replacement question for this question, which has been investigated by the GrowingIO front-end engineer post.

Since the nth step must come from n-1 or n-2, the number of the nth step is the number of the upper (n-1) step "plus" the upper (n-2) step The number`.

Recursive code:

function climbStairs(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

We continue to use a recursion tree to intuitively feel the following:

dynamic-programming-2

Red indicates repeated calculations

It can be seen that there are a lot of repeated calculations, we can use a hashtable to cache the intermediate calculation results, thereby eliminating unnecessary calculations.

So how does dynamic programming solve this problem? The answer is also "look up the table", but different from using the function call stack recursively, dynamic programming usually uses the dp array, the index of the array is usually the problem size, and the value is usually the return value of the recursive function. Recursion is to deduct from the result of the problem until the size of the problem is reduced to normal. Dynamic planning starts from the usual and gradually expands the scale to the optimal substructure.

If the above problem of climbing stairs, using dynamic programming, the code is like this:

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];
}

No, it doesn't matter, let's modify the recursive code a bit. In fact, change the name of the function:

function dp(n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  return dp(n - 1) + dp(n - 2);
}

Compare dp[n] and dp(n). Does this make sense? It just uses the call stack to enumerate state recursively, while dynamic programming uses iterative enumeration state.

If the table lookup process of dynamic programming is drawn as a picture, it is like this:

dynamic-programming-3

The dotted line represents the look-up process

This problem is the simplest problem in dynamic programming, because it only involves the change of a single factor. If multiple factors are involved, it is more complicated, such as the famous backpack problem, gold mining problem, etc.

For a single factor, we only need a one-dimensional array at most. For the knapsack problem, we need a two-dimensional or even higher-dimensional array.

We do not need to use a one-dimensional array to climb the stairs, but use two variables to achieve it, and the space complexity is O(1). Code:

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

  let a = 1;
  let b = 2;
  let temp;

  for (let i = 3; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }

  return temp;
}

This is possible because the current state is only related to the first two states in the state transition equation of the staircase climbing problem, so only these two needs to be stored. There are many such tricky methods for dynamic programming problems. This technique is called rolling arrays.

To emphasize again:

-If we say that recursion is to deduct from the result of the problem, until the problem size is reduced to normal. Then dynamic programming is to start from the usual and gradually expand the scale to the optimal substructure. -There is no essential difference between memoized recursion and dynamic programming. They are all enumerated states, and are gradually derived and solved according to the direct connection of the states. -Dynamic programming performance is usually better. On the one hand is the stack overhead of recursion, on the other hand is the technique of scrolling arrays.

Three elements of dynamic programming¶

:::tip

Critical conditions
State transition equation
Enumeration states :::

It can be seen that the same idea is used for recursive solution

In the problem of climbing stairs explained above, if we use f(n) to indicate how many ways there are to climb n steps, then:

f(1) and f(2) are [boundary]
f(n) = f(n-1) + f(n-2) is the [state transition formula]

Let me express it in the form of dynamic programming:

dp[0] and dp[1] are [boundary]
dp[n] = dp[n-1] + dp[n-2] is the [state transition equation]

You can see how similar the two are.

In fact, the critical conditions are relatively simple. You only have to write a few more questions to get a sense of it. The difficulty is to find the state transition equation and enumerate the state. Both of these core points are based on the already abstracted state. For example, the problem of climbing stairs, if we use f(n) to indicate how many ways there are to climb n steps, then f(1), f(2), ... are each independent state.

However, the definition of state has its own unique routines. For example, the status of a string is usually dp[i] which means that the string s ends with i.... For example, the status of two strings is usually dp[i][j], which means that the string s1 ends with i and s2 ends with j....

Of course, there may be more than one state transition equation, and the corresponding efficiencies of different transition equations may also be quite different. This is a relatively metaphysical topic and requires everyone to understand in the process of doing the problem.

After getting the definition of state, let's look at the state transition equation.

State transition equation¶

The problem of climbing stairs. Since the n-th step must come from n-1 or n-2, the number of the n-th step is the number of (n-1) steps "plus" (n-2) ) The number of steps`.

The above understanding is the core, it is our state transition equation, expressed in code is f(n) = f(n-1) + f(n-2).

The actual operation process may be as intuitive as climbing stairs, and it is not difficult for us to think of it. It may also be hidden deep or too high in dimension. If you really can't think of it, you can try to draw a picture to open your mind. This is also the method when I first learned dynamic programming. When you get the amount of questions, your sense of question will come, and you don't need to draw pictures at that time.

There is really no panacea for the state transition equation. Different problems have different solutions. The state transition equation is also the most difficult and critical point in solving dynamic programming problems. You must practice more to improve the sense of the problem. Next, let's take a look at the less difficult, but more novice questions-how to enumerate states.

How to enumerate states¶

The key to enumerating states is how to enumerate states so that they are not repeated.

If it is a one-dimensional state, then we can use a layer of loop to get it done.
If it is a two-dimensional state, then we can use a two-layer loop to get it done.
. . .

This can ensure that there is no repetition and no omission.

But the actual operation process has many details such as:

Do I enumerate the one-dimensional state first on the left or on the right? (Traversal from left to right or from right to left)
Do I first enumerate the upper left or upper right, lower left or lower right of the two-dimensional status?
The positional relationship between the inner loop and the outer loop (can they be interchanged)
. . .

In fact, this thing is related to many factors, it is difficult to summarize a law, and I think it is completely unnecessary to summarize the law. But here I still summarize a key point, that is:

If you do not use the technique of scrolling arrays, then the traversal sequence depends on the state transition equation. such as:

for i in range(1, n + 1):
  dp[i] = dp[i-1] + 1;

Then we need to traverse from left to right, the reason is very simple, because dp[i] depends on dp[i-1], so when calculating dp[i], dp[i-1] needs to be already calculated.

Two-dimensional is the same, you can try it.

If you use the technique of scrolling arrays, you can traverse any way, but different traversal meanings are usually not different. For example, I compressed the two-dimensional to one-dimensional:

for i in range(1, n + 1):
  for j in range(1, n + 1):
    dp[j] = dp[j-1] + 1;

This is okay. dp[j-1] actually refers to dp[i][j-1] before compression

and:

for i in range(1, n + 1):
  # Reverse traversal
  for j in range(n, 0, -1):
    dp[j] = dp[j-1] + 1;

This is also possible. But dp[j-1] actually refers to dp[i-1][j-1] before compression. Therefore, what kind of traversal method is used in practice depends on the topic. I specially wrote a [Complete Knapsack Problem] Routine Problem (1449. Digit Cost and Maximum Number of Target Value article, through a specific example to tell you the different traversals What is the actual difference, I strongly recommend everyone to take a look and give it a triple.

-Regarding the inside and outside circulation, the principle is similar to the above.

This is more subtle, you can refer to this article to understand 0518.coin-change-2.

Summary¶

How to determine the critical condition is usually relatively simple, and you can quickly master it by doing a few more questions.

Regarding how to determine the state transition equation, this is actually more difficult. Fortunately, these routines are relatively strong, such as the state of a string, usually dp[i] means that the string s ends with i.... For example, the status of two strings is usually dp[i][j], which means that the string s1 ends with i and s2 ends with j.... In this way, when you encounter a new problem, you can apply it. If you can't find it, draw the picture honestly and observe continuously to improve the sense of the problem.

Regarding how to enumerate the state, if there is no scrolling array, then how to enumerate can be determined according to the transition equation. If you use a rolling array, you should pay attention to the dp correspondence between after compression and before compression.

Why do dynamic planning draw a table¶

The problem of dynamic programming is to draw a table, but some people don’t know why they want to draw, they think this is inevitable, and it is necessary to draw a table to be dynamic programming.

In fact, dynamic programming essentially transforms a big problem into a small problem, and then the solution of the big problem is related to the small problem. In other words, the big problem can be calculated from the small problem. This is the same as using recursive solution, but dynamic programming is a similar look-up table method to reduce time complexity and space complexity.

The purpose of drawing the table is to continuously derive and complete the state transition. Each cell in the table is a small problem. The process of filling in the table is actually the process of solving the problem.

We first solve the case where the scale is normal, and then gradually derive based on this result. Normally, the lower right corner of the table is the largest scale of the problem, which is the scale we want to solve.

For example, when we use dynamic programming to solve the knapsack problem, we are actually constantly asking according to the previous small question A[i-1][j] A[i -1][w-wj]:

Should choose it
Still not choosing it

As for the criterion of judgment, it is very simple, that is, the value is the largest. Therefore, what we have to do is to find the value of the two cases of choice and non-selection, and then take the largest value, and finally update the cell.

In fact, most of the dynamic programming problem routines are "choice" or "no choice", that is to say, it is a kind of "multiple choice". And most dynamic programming problems are accompanied by space optimization (rolling array), which is the advantage of dynamic programming over traditional memoized recursion. In addition to this advantage, the use of dynamic programming mentioned above can reduce the function call stack generated by recursion, so the performance is better.

to sum up¶

This article summarizes two commonly used methods in algorithms-recursion and dynamic programming. If you are recursive, you can practice with the topic of the tree. If you are dynamic programming, you can brush up on the recommendations I recommended above, and then consider brushing the dynamic programming label of Likou.

When you learn dynamic programming in the early stage, you can try to solve it with memoization first. Then transform it into dynamic programming, so that you will feel it when you practice it a few times. After that, you can practice scrolling the array. This technique is very useful and relatively simple. The difficulty of comparing dynamic programming lies in enumerating all states (no repetition) and finding state transition equations.

If you can only remember one sentence, then please remember: Recursion is to reverse the result of the problem until the size of the problem is reduced to normal. Dynamic planning starts from the usual and gradually expands the scale to the optimal substructure.

In addition, you can go to Recursion I in LeetCode Exploration for interactive learning.

Recursion and Dynamic programming¶

Recursion¶

Practice recursion¶

Repeated calculation in recursion¶

Summary¶

Dynamic planning¶

Explosion stack¶

Repeated calculation¶

Three elements of dynamic programming¶

State transition equation¶

How to enumerate states¶

Summary¶

Why do dynamic planning draw a table¶

related question¶

to sum up¶