“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”
The title
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:
- Right -> right -> down -> down
- Down -> down -> right -> right
Train of thought
Simple dynamic programming problems, on the solution of each grid by a combined to get the result of the grid and the grid, a grid or on the left pane may be empty or obstacles, if there are obstacles on the left, at this time by the results of the above grid have inherited the grid, in the same way the grid if there are obstacles from the left have inherited, Inheritance is not the right word, but let’s just say that for now. The dynamic programming equation is as follows
There are some places that need to pay attention to, some of which I did not think of at the beginning, it is indeed a mistake, next time the same kind of topic need to pay attention to: 1. When there is an obstacle at the beginning or end 2. When there is an obstacle in one or a row, there is no obstacle 1 and 0, 3. If the grid is tempArray[I][j], tempArray[I][j] = tempArray[i-1][J] + tempArray[I][J-1]; 4. Be sure to pay attention to boundary conditions and concomitants
code
<script> var uniquePathsWithObstacles = function (obstacleGrid) { let tempArray = obstacleGrid; let rowlength = tempArray.length; // let collength = tempArray[0].length; / / column let res; / / in single row or single case judgment, as long as there is an obstruction result is 0, or 1 if (rowlength = = = 1 | | collength = = = 1) {let bool = false; for (let i = 0; i < rowlength; i++) { for (let j = 0; j < collength; j++) { if (tempArray[i][j] === 1) { bool = true; break; } } } if (bool) { console.log(0); return; } else { console.log(1); return; }} // Judge the start and end, With an obstacle has a direct returns 0 if the result (tempArray [rowlength - 1]] [collength - 1 = = = 1 | | tempArray [0] [0] = = = 1) {the console. The log (0); return; } // for (let I = 0; i < rowlength; i++) { for (let j = 0; j < collength; j++) { if (tempArray[i][j] === 1) { tempArray[i][j] = -1; } rowTemp = 1;} rowTemp = 1; for (let j = 0; j < collength; j++) { if (tempArray[0][j] === -1) { rowTemp = -1; tempArray[0][j] = rowTemp; } else { tempArray[0][j] = rowTemp; } } let colTemp = 1; for (let i = 0; i < rowlength; i++) { if (tempArray[i][0] === -1) { colTemp = -1; tempArray[i][0] = colTemp; } else { tempArray[i][0] = colTemp; } } for (let i = 1; i < rowlength; i++) { for (let j = 1; j < collength; j++) { if (tempArray[i][j] ! == -1) { tempArray[i][j] = tempArray[i - 1][j] + tempArray[i][j - 1]; } if (tempArray[i - 1][j] === -1 && tempArray[i][j] ! == -1) { tempArray[i][j] = tempArray[i][j - 1] } if (tempArray[i][j - 1] === -1 && tempArray[i][j] ! == -1) { tempArray[i][j] = tempArray[i - 1][j] } } } if (tempArray[rowlength - 1][collength - 1] === -1) { res = 0 } else { res = tempArray[rowlength - 1][collength - 1]; } console.log(res); console.log(tempArray); }; uniquePathsWithObstacles([ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ]) uniquePathsWithObstacles([ [0, 0, 0], [0, 1, 0], [0, 0, 0] ]) uniquePathsWithObstacles([ [0, 1], [0, 0] ]) uniquePathsWithObstacles([ [0, 0], [0, 1] ]) uniquePathsWithObstacles([ [0, 0, 1, 0] ]) uniquePathsWithObstacles([ [0, 1], [1, 0] ]) uniquePathsWithObstacles([ [0, 0], [1, 1], [0, 0] ]) uniquePathsWithObstacles([ [0, 1, 0], [1, 0, 0], [0, 0, 0] ]) uniquePathsWithObstacles([ [0, 1, 0, 0], [0, 0, 0, 0], [1, 0, 1, 0], [0, 0, 1, 0] ]) uniquePathsWithObstacles([ [0, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ]) </script>Copy the code
instructions
Was used for learning, the authors of this article is to LeetCode brush what you see is what you want, quoting the part of the power resources, the code is written according to bosses thought, than the bosses of the code, my code must have a large optimization space, if the button is suggested that access to learn force website to learn, this blog only record my growing up!