“Xiao Wang, Xiao Zhang and Xiao Zhao are good friends. One of them went into business, one was admitted to a key university, and the other joined the army. In addition, they knew the following conditions: Xiao Zhao was older than the soldier; The college student is younger than Xiao Zhang; Xiao Wang’s age is different from that of a college student. Which of these three men is the businessman? Who is a college student? Who is a soldier?

This article aims to document some dp training questions, if you are not familiar with dynamic programming, please refer to this article

—-

How do I explain dynamic programming to my 5-year-old niece?

—-

There is a long way to go

What problem can I choose to do dynamic programming?

Counting 1.

  • How many ways can I get to the bottom right corner
  • How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

  • The maximum numeric sum of the path from the upper left corner to the lower right corner
  • Maximum ascending subsequence length

3. Seek existence

  • Stone game, whether the first hand will win
  • Can we pick k numbers such that the sum is sum

Subject to a

63. Different paths II

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).

Now consider that there are obstacles in the grid. So how many different paths are there going to be from the top left to the bottom right?

Obstacles and empty positions in the grid are represented by 1 and 0 respectively.

Example 1:

Enter: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output: 2

Explanation:

There is an obstacle right in the middle of the 3×3 grid.

There are two different paths from the top left to the bottom right:

\1. Right -> right -> down -> down

\2. Down -> down -> right -> right

Example 2:

Enter: obstacleGrid = [[0,1],[0,0]]

Output: 1.

Tip:

m == obstacleGrid.length

n == obstacleGrid[i].length

1 <= m, n <= 100

ObstacleGrid [I][j] is 0 or 1

Subject to

—

How do I explain dynamic programming to my 5-year-old niece?

—

The different paths 1 are roughly the same, but with the addition of obstacles, we just need to make a judgment that there are no obstacles.

2.1. Dynamic planning component 1: State determination

The last step

No matter how the robot reaches the bottom right corner, there is always a final move: – to the right or down

If I show, let’s call the bottom right corner m minus 1,n minus 1.

So the position of the robot before the last step is either (m-2,n-1) or (m-1,n-2).

subproblems

So, if the robot has x ways to go from the top left corner to (m-2,n-1), and Y ways to go from the top left corner to (m-1,n-2), then the robot has x +Y ways to go to (m-1,n-1).

The question becomes, how many ways can the robot go from the top left corner to (m-2,n-1) or (m-1,m-2)?

If go to is (m-2,n-1) as shown in the figure:

We can just kill the last column

Similarly, if you go to m minus one,n minus two, you’re going to lose one row.

Status:

Let f[I][j] be how many ways can the robot go from the top left corner to (I,j)

2.2. Dynamic programming component 2: Transfer equation

For any cell:

f[i][j] = f[i-1][j] + f[i][j-1]

1 2 3

1 represents how many ways the robot can go to [I][J]

2 represents how many ways the robot can go to F [i-1][J]

3 represents how many ways the robot can go to F [I][J-1]

2.3. Dynamic programming component 3: Initial conditions and boundary cases

Initial condition: f[0][0]=1, because the robot has only one way to get to the top left corner

Boundary case: I =0 or j=0, then the previous step can only have one direction, that is, the 0th row or the 0th column, each step has only one case, then f[I][j] = 1, the other regions satisfy the transfer equation.

If an obstacle is encountered, f[I][j] = 0.

3.4. Dynamic programming component 4: Order of calculation

Row by row. Why row by row?

When f[1][1] is calculated, both f[0][1] and f[1][0] have already been calculated, and these two coordinates have also been calculated by column, so there is no need to calculate them again.

  • F [0][0]= 1 if the first is an obstacle F [0][0]=0
  • Calculate line 0: f[0][0], F [0][1]… ,f[0][n-1]
  • Calculate line 1: f[1][0], F [1][1]… ,f[1][n-1]
  • .
  • Calculate line m-1: f[m-1][0], F [m-1][1]… ,f[m-1][n-1]

Time complexity: O(Mn)

Reference code

class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid == null || obstacleGrid.length == 0) {
        return 0;
    }

    // Define the dp array and initialize row 1 and column 1.
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m && obstacleGrid[i][0] = =0; i++) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
        dp[0][j] = 1;
    }

    / / based on state transition equation dp [I] [j] = dp [j] + [I - 1] dp [I] [1] for recurrence.
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; }}}return dp[m - 1][n - 1];
}
Copy the code

Just to give you a quick version of the scrolling array, once we know the maximum number of paths at the current location, we can find the number of paths at the next location, just the one on the left and the one on the top, order of m.

Reference code

  public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int n = obstacleGrid.length, m = obstacleGrid[0].length;
    int[] f = new int[m];

    f[0] = obstacleGrid[0] [0] = =0 ? 1 : 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (obstacleGrid[i][j] == 1) {
                f[j] = 0;

            } else 
            if (j - 1> =0 && obstacleGrid[i][j - 1] = =0) {
                f[j] += f[j - 1]; }}}return f[m - 1];

}
Copy the code

Top recommendations:

  • [Today’s Leecode] Add two numbers

  • ThreadPoolExecutor ThreadPool

  • Swastika parsing: Recently, the service is ready to go live, adding JVM parameters to the microservice

  • Wanwen long word analysis: want to enter big factory, you have to master the CPU cache foundation

  • How do I explain dynamic programming to my 5-year-old niece?

  • 【 Dynamic programming Day One – longest loop substring 】

  • Dynamic Programming Day Two-regular expression matching

  • [Dynamic planning Day four- Rain water]

  • 【 Dynamic programming Day Five- Wildcard matching 】

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… More information will follow.