Problem¶

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10**9.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0|0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:

1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0|0,1],[0,0]]
Output: 1

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

Solve¶

Dynamic programming¶

O(n ** 2)

By using this information:

The robot can only move either down or right at any point in time.

We can use this formula to calculate the total bot path, adding up the possibility in go down and go right movement of the bot:

totalPath[x][y] = totalPath[x-1][y] + totalPath[x][y-1] 

Final implementation look like this

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int path[obstacleGridSize][*obstacleGridColSize];
    path[0][0] = !obstacleGrid[0][0];
    for (int i = 0; i < obstacleGridSize; i ++)
        for (int j = 0; j < *obstacleGridColSize; j++) {
            if (i == j && j == 0) continue;
            path[i][j] = 0;
            if (obstacleGrid[i][j] == 1) continue;
            if (i > 0)
                path[i][j] += path[i-1][j];
            if (j > 0)
                path[i][j] += path[i][j-1];
        }
    return path[obstacleGridSize-1][*obstacleGridColSize-1];
}

Comparison¶

• java: While we can direct transfer path[0][0] = obstacleGrid[0][0] ^ 1 , here I try inline if
  

  class Solution {
      public int uniquePathsWithObstacles(int[][] obstacleGrid) {
          int m = obstacleGrid.length;
          int n = obstacleGrid[0].length;
          int[][] path = new int[obstacleGrid.length][obstacleGrid[0].length];
  
          path[0][0] = (obstacleGrid[0][0] == 0) ? 1 : 0;
  
          for (int i = 0; i < m; i ++)
              for (int j = 0; j < n; j++) {
                  if (obstacleGrid[i][j] == 1) continue;
                  if (i > 0)
                      path[i][j] += path[i-1][j];
                  if (j > 0)
                      path[i][j] += path[i][j-1];
              }
          return path[m-1][n-1];
      }
  }
  

• c): Randomly with time to complete the problem (it should always be0msimo), but it quite nice to have1, 0 -> 0, 1convert using!(notlogical operand path[0][0] = !obstacleGrid[0][0]; Also, i don’t used memset to initialized path = {0}

• python): I just directly convert usingint(`` value
  

  class Solution:
      def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
          m = len(obstacleGrid)
          n = len(obstacleGrid[0])
          path = [[0] * n for _ in range(m)]
  
          path[0][0] = int(obstacleGrid[0][0] == 0)
  
          for i in range(m):
              for j in range(n):
                  if i == j == 0 or obstacleGrid[i][j] == 1:
                      continue
                  if i > 0:
                      path[i][j] += path[i-1][j]
                  if j > 0:
                      path[i][j] += path[i][j-1]
          return path[m-1][n-1]
  

• rust): feel like java code, nothing fancy (while I do have to go back and remove some unused code injavasolution to matchrustversion
  

  impl Solution {
      pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
          let m = obstacle_grid.len();
          let n = obstacle_grid[0].len();
          let mut path = vec![vec![0; n]; m];
  
          path[0][0] = obstacle_grid[0][0] ^ 1;
  
          for i in 0..m {
              for j in 0..n {
                  if obstacle_grid[i][j] == 1 {
                      continue;
                  }
                  if i > 0 {
                      path[i][j] += path[i - 1][j];
                  }
                  if j > 0 {
                      path[i][j] += path[i][j - 1];
                  }
              }
          }
  
          path[m - 1][n - 1]
      }
  }