# 63. Unique Paths II

## Approach 1: 2D DP

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: int uniquePathsWithObstacles(vector>& obstacleGrid) { const int m = obstacleGrid.size(); const int n = obstacleGrid[0].size(); // dp[i][j] := unique paths from (0, 0) to (i - 1, j - 1) vector> dp(m + 1, vector(n + 1, 0)); dp[0][1] = 1; // Can also set dp[1][0] = 1 for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (!obstacleGrid[i - 1][j - 1]) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return dp[m][n]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { final int m = obstacleGrid.length; final int n = obstacleGrid[0].length; // dp[i][j] := unique paths from (0, 0) to (i - 1, j - 1) long[][] dp = new long[m + 1][n + 1]; dp[0][1] = 1; // Can also set dp[1][0] = 1 for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (obstacleGrid[i - 1][j - 1] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return (int) dp[m][n]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m = len(obstacleGrid) n = len(obstacleGrid[0]) # dp[i][j] := unique paths from (0, 0) to (i - 1, j - 1) dp = [[0] * (n + 1) for _ in range(m + 1)] dp[0][1] = 1 # Can also set dp[1][0] = 1 for i in range(1, m + 1): for j in range(1, n + 1): if obstacleGrid[i - 1][j - 1] == 0: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[m][n] 

## Approach 2: 1D DP

• Time: $O(mn)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: int uniquePathsWithObstacles(vector>& obstacleGrid) { const int m = obstacleGrid.size(); const int n = obstacleGrid[0].size(); vector dp(n); dp[0] = 1; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (obstacleGrid[i][j]) dp[j] = 0; else if (j > 0) dp[j] += dp[j - 1]; return dp[n - 1]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { final int m = obstacleGrid.length; final int n = obstacleGrid[0].length; int[] dp = new int[n]; dp[0] = 1; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (obstacleGrid[i][j] == 1) dp[j] = 0; else if (j > 0) dp[j] += dp[j - 1]; return dp[n - 1]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m = len(obstacleGrid) n = len(obstacleGrid[0]) dp = [0] * n dp[0] = 1 for i in range(m): for j in range(n): if obstacleGrid[i][j]: dp[j] = 0 elif j > 0: dp[j] += dp[j - 1] return dp[n - 1]