Original link: leetcode-cn.com/problems/un…

Answer:

  1. At any point in the grid, there are two ways to go right and two ways to go down. It also comes from the top and the left.
  2. So, the number of moves at any point is equal to the sum of the number of moves from the starting point to the top and the left.
  3. There’s only one way to go from the first row to the first column, which is to go all the way to the end.
  4. We can take a two-dimensional array, plot the number of moves at each point in the grid, and then recurse all the way to the end point, where all the moves are stored.
  5. Therefore, the state transition equation of dynamic programming is:dp[i][j]=dp[i-1][j]+dp[i][j-1].
  6. If an obstacle is encountered, the number of moves at that position is 0.
/ * * *@param {number[][]} obstacleGrid
 * @return {number}* /
var uniquePathsWithObstacles = function (obstacleGrid) {
  // Cache the last bit index of the grid column
  const m = obstacleGrid.length - 1;
  const n = obstacleGrid[0].length - 1;

  // If the start or end is 1, the number of paths is 0
  if (obstacleGrid[0] [0= = =1 || obstacleGrid[m][n] === 1) {
    return 0;
  }

  // Initialize the dp array on the first line, starting with a value of 1
  let dp = [new Array(n + 1).fill(0)];
  dp[0] [0] = 1;

  // Create the initial number of paths for column 1
  for (let i = 1; i <= m; i++) {
    // Initializes the number of paths for the current row. Default is 0
    dp.push(new Array(n + 1).fill(0));

    if (obstacleGrid[i][0= = =0) {
      // If the current position can walk, the number is equal to the previous row
      dp[i][0] = dp[i - 1] [0];
    } else {
      // If the current position is not walkable, the number is 0
      dp[i][0] = 0; }}// Initialize the number of paths in the first row
  for (let i = 0; i <= n; i++) {
    if (obstacleGrid[0][i] === 0) {
      // If the current position can walk, the number is 1
      dp[0][i] = 1;
    } else {
      // If the current position is not walkable, the number from then on is 0
      // The first line is initialized with a value of 0
      break; }}// Count the number of paths through the grid starting from row 2 and column 2
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (obstacleGrid[i][j] === 0) {
        // If the current position can walk, the number of paths is the sum of the number of paths from the top and left directions
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      } else {
        // If the current position is unwalkable, the number of paths is 0
        dp[i][j] = 0; }}}// The endpoint stores the number of paths
  return dp[m][n];
};
Copy the code
  1. In fact, when we calculate the number of steps at a point, we just need the left and top values.
  2. We can use just one array, and we generate the number of steps from left to right each time, so we have the following characteristics:
    • So for row MTH, it stores the number of steps in row m-1.
    • For the NTH column, its n-1 position stores the number of steps at the n-1 position.

The code optimization is as follows:

/ * * *@param {number[][]} obstacleGrid
 * @return {number}* /
var uniquePathsWithObstacles = function (obstacleGrid) {
  // Cache the last bit index of the grid column
  const m = obstacleGrid.length - 1;
  const n = obstacleGrid[0].length - 1;

  // If the start or end is 1, the number of paths is 0
  if (obstacleGrid[0] [0= = =1 || obstacleGrid[m][n] === 1) {
    return 0;
  }

  // Initialize the dp array on the first line, starting with a value of 1
  let dp = new Array(n + 1).fill(0);
  dp[0] = 1;

  // Count the number of paths through the grid starting from row 2 and column 2
  for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
      // If the current position is an obstacle, the number of paths is 0
      if (obstacleGrid[i][j] === 1) {
        dp[j] = 0;
        continue;
      }

      // if j is 0, it does not need to be updated
      if (j > 0) {
        // If the current position can walk, the number of paths is the sum of the number of paths from the top and left directions
        dp[j] = dp[j - 1] + dp[j]; }}}// The endpoint stores the number of paths
  return dp[n];
};
Copy the code