I. Introduction case

First, let’s look at a typical example to see what dynamic programming is.

A frog can jump up one step or two at a time. Find out how many ways the frog can jump up n steps.

This topic, which comes up frequently in some interviews, is the DP of dynamic programming algorithm. So how do we do that?

1. Create an array to store hops to layer N

Suppose such an array arr, arr[n] represents the hop to layer n, arr[n-1] represents the hop to layer n-1. We don’t have to worry about what arr[n] is going to be.

2, backward analysis, find the relationship

Normal situation, if climb up from the 1st, can climb 2, also can climb 3. It is too difficult for us to enumerate in the positive direction. So, we’re going to do it backwards.

If the frog climbs up, it can only climb up from n-1(penultimate layer), or n-2(penultimate layer). If the frog reaches n-1, the cumulative jump is ARR [n-1]. If the frog reaches n-2, the cumulative jump is ARR [n-2].

Then, the total jump to the NTH floor is:

arr[n] = arr[n-1] + arr[n-2]
Copy the code

Now, isn’t that a little bit like the way we used to do math by induction?

3. Deal with extreme values

Obviously, the stairs can only be positive. Arr [n] = arr[n-1] + arr[n-2], where n, if it is 1, requires special treatment.

Arr [1] is obviously equal to one, because there is only one way to jump to level 1. Arr [2] is obviously equal to 2, because at level 2, there are two jumps.

so

arr[1] = 1;
arr[2] = 2;
arr[0] = 0;
Copy the code

So the final implementation method is as follows:

function dpClimb(n){
    if(n<=2){
        returnn; // n = 0,1,2}return dpClimb(n-1) + dpClimb(n-2)
}
Copy the code

Didn’t I just say I put it in an array? How did it become dpClimb(n) and dpClimb(n-1)? In this case, dpClimb(n) returns a value representing the number of hops to the NTH level (an invisible array, if you like). We use recursion. At the same time, we used some cache. By caching the hops of the first two layers, we know the hops of the third layer.

Test how many ways you can climb 20 flights of stairs:

Ii. In-depth case study

Last time we thought of it as a one-dimensional array, this time we’re going to do a two-dimensional array.

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below). The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below). How many different paths are there?

We implement this step by step as we did in the previous step.

1. Create an array to store hops to layer N.

Now that we have a two-dimensional array, we use arr[m-1][n-1] to represent the sum of the paths to the [m,n] cell. Why arR [m-1][N-1]? Because you can only move one cell at a time, and the array starts at [0,0].

2, backward analysis, find the relationship

Assuming that the robot is at [I,j], its last move can only be from [I, J-1], or [I-1,j]. So, the sum of the paths to [I,j] is:

arr[i][j] = arr[i-1][j] + arr[i][j-1]
Copy the code

3. Handle extreme values (initial values)

Here, we can only start at the coordinates [0,0], so I and j are both greater than or equal to 0. At the same time, when the robot is walking horizontally or vertically along the edge of the grid, at the same time, they want the robot to only go down or to the right (not to the left, but up). So, when you put the robot on the edge of a cell, no matter which cell it is on, the sum of the paths to that cell can only be 1.

Therefore, we get the extreme value as:

arr[i][0] = 1;
arr[0][j] = 1;
Copy the code

Code implementation

// Start by defining an empty JavaScript 2d arrayfunction Array2(m,n){
    let _array2 = new Array(m);
    for(leti=0; i<m; i++){let emptyArr = new Array(n);
        for(letj=0; j<n; j++){ emptyArr[j] = 0; } _array2[I] = emptyArr;} _array2[I] = emptyArr; }return_array2; } the console. The log (Array2 (6, 7));Copy the code

Verify that the two-dimensional array method is what we want:

So we have this two-dimensional array, and we can store arr[I][j].

The main code is as follows:

function totalPath(m,n){
    letarr = Array2(m,n); // The extreme case of walking sidewaysfor(leti=0; i<m; i++){ arr[i][0] = 1; } // Vertical down the extremum casefor(letj=0; j<n; j++){ arr[0][j] = 1; } // Relational generalizationfor(leti=1; i<m; i++){for(letj = 1; j<n; j++){ arr[i][j] = arr[i-1][j] + arr[i][j-1]; }}return arr[m-1][n-1];
}
Copy the code

Let’s look at the results

The console. The log (totalPath (7, 3));Copy the code

At the same time, we can also see that cached array, storing the sum of the paths to each grid coordinate.

conclusion

From the first example, we used recursion, and from the second example, we used caching. Therefore, DP dynamic programming can be preliminarily understood as the use of recursion + cache to solve certain kinds of problems. As for time complexity, space complexity, and so on understanding, and then optimize.