This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.
【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.
Then do it! This column is all about dynamic planning, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. There isn’t much about dynamic programming, but it’s a must for every programmer
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
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 codeJust 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 codeThank you for reading this, if this article is well written and if you feel there is something to it
Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!
If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️