This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

Different paths

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?

Example 1:

Input: m = 3, n = 7 Output: 28 Example 2:

Input: m = 3, n = 2 Output: 3 Description: There are three paths to the lower right corner starting from the upper left corner.

  1. Right -> down -> down
  2. Down -> down -> to the right
  3. Down -> right -> down

Example 3:

Input: m = 7, n = 3 Output: 28 Example 4:

Input: m = 3, n = 3 Output: 6

Second, train of thought analysis

  • Again, addressing, again, how many ways there are. Again, you need to solve the problem step by step. I’m saying that now if you don’t know how to do dynamic programming, I don’t know what to say.
  • Of course, there are many ways to solve problems. I’m just suggesting dynamic programming to solve the problem or to enhance our familiarity with dynamic programming. It’s not that the problem has to go back

Transfer equation

  • First of all, let’s think about the problem of finding a path, and we’re directly exposed to the idea that there are no dimensions, only differences in execution and manner. But ontology is a two-dimensional problem, so we need to use two-dimensional array to help us store small problems.
  • Let’s first stipulatedp[i][j]I’m going from the top left corner of the map to (I,j)

  • So let’s think about it, if we want to go from 0,0 to big (I, j), what do we do? They also tell us that we can only go down or to the right. That means we can only move by increasing I or increasing j.
  • So let’s think about which points can be increased by increasing I or by increasing j to be greater (I,j).

  • Above is a diagram drawn by the author. According to the diagram, it should be obvious that there are two nodes that can be legally moved to large (I, j).
  • So there are (I -1,j),(I,j-1) nodes. The sum of the paths to the big two nodes is thetadp[i][j]The value of the
  • I don’t know if you noticed, but it’s a little bit special if the robot ZXhTom walks on the edge, which is actually a boundary problem

  • When a robot walks on a boundary, its source can only be one up the axis. Since the other node is a nonexistent node, we can interpret it as a state in which the route is blocked. So the final state transition equation we have is as follows

d p [ i ] [ j ] = d p [ i – 1 ] [ j ] + d p [ i ] [ j – 1 ] dp[i][j]=d p[i-1][j]+d p[i][j-1]
  • But there’s a special point to be made here whendp[i][j]Its value is 0 when representing a virtual space address.

The initial value

  • The initial value isdp[0][0]=1. This might be a little abstract.dp[0][0]There is no way to move down or right in the upper left corner, because it is just marking time. That’s a little bit off the mark.
  • But it’s a lot easier to explain it backwards becausedp[0][1]=dp[0][0]. sodp[0][0]=1 .
  • Another point we can understand is that the initial position of the robot needs to be placed by our program. Placement can be understood as one step in place. sodp[0][0]=1

Start small and start big

  • The transfer equation is determined and the initial value is determined. From small to large is a loop through it.

AC code

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    dp[0] [0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) {
                continue;
            }else if (i == 0) {
                dp[i][j] = dp[i][j - 1];
            } else if (j == 0) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; }}}return dp[m-1][n-1];
}
Copy the code
  • Since we are walking on a two-dimensional map, we need a two-dimensional array to store the corresponding data. It’s the same as climbing the stairs. We don’t need to store all the details here, we just need to store the left and top nodes associated with the current node. This way the author here is not to achieve. If not, you can find the “Climbing stairs” section on the home page to see the logic

upgrade

  • The above dynamic programming solution is perfect, because we don’t need to consider complex cases, just need three axe to solve. And the execution efficiency is really unspeakable. The fly in the ointment is that memory consumption is a bit imperfect.
  • The author’s optimization idea also mentioned above, simplified dp array, but in the end, it seems that DP can not be simplified, so this idea was abandoned. Later, I looked at the recommendation algorithm on the official website. In addition to dynamic programming they also have a method called permutation and combination.

  • No matter how you go, you can’t go back so the total number of steps is fixed, exactly the total number of horizontal steps and the total number of strides are fixed.
  • We have horizontal and vertical relative to each other in the exact point of the number of steps. For example, in the case of 7 total steps, if there are 3 horizontal steps, then there must be 4 vertical steps left. So all we need to do is figure out all the permutations of the three horizontal steps.
  • And since we’re all starting at zero in our memory, our total steps in the m by n matrix are zero(m-1)+(n-1), so we just need tom-2To find out in them-1A medium will probably do. Here is a formula from the official website

C m + n – 2 m – 1 = ( m + n – 2 m – 1 ) = ⟨ m + n – 2 } ( m + n – 3 ) … n ( m – 1 ) ! = ( m + n – 2 ) ! ( m – 1 ) ! ( n – 1 ) ! C_{m+n-2}^{m-1}=\left(\begin{array}{c} m+n-2 \\ m-1 \end{array}\right)=\frac{\langle m+n-2\}(m+n-3) \cdots n}{(m-1) ! }=\frac{(m+n-2) ! }{(m-1) ! (n-1) ! }

  • Finally, we just need to write the code for the above formula. I have to say that the mathematical derivation of the program is really good. But such code is difficult for others to understand. Here readers have not tried to use the official website code directly.

  • We ended up running much higher in memory than we did. Here I just want to make the difference between the two contrasts. The main content of this article is to introduce how the concept of dynamic programming is implemented.

Four,

  • In this paper, the author mainly introduces how to analyze and solve problems through dynamic return through a case list
  • Understand the nature of dynamic programming through the three axes. I’m sure you’ll understand the dynamic programming problem a little bit

I don’t have any hobbies. I just like you to like, follow and comment