Well, this problem is similar to Unique Paths. The introduction of obstacles only changes the boundary conditions and make some points unreachable (simply set to 0
).
Denote the number of paths to arrive at point (i, j)
to be P[i][j]
, the state equation is P[i][j] = P[i - 1][j] + P[i][j - 1]
if obstacleGrid[i][j] != 1
and 0
otherwise.
Now let's finish the boundary conditions. In the Unique Paths problem, we initialize P[0][j] = 1, P[i][0] = 1
for all valid i, j
. Now, due to obstacles, some boundary points are no longer reachable and need to be initialized to 0
. For example, if obstacleGrid
is like [0, 0, 1, 0, 0]
, then the last three points are not reachable and need to be initialized to be 0
. The result is [1, 1, 0, 0, 0]
.
Now we can write down the following (unoptimized) code. Note that we pad the obstacleGrid
by1
and initialize dp[0][1] = 1
to unify the boundary cases.
1 class Solution { 2 public: 3 int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { 4 int m = obstacleGrid.size(), n = obstacleGrid[0].size(); 5 vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0)); 6 dp[0][1] = 1; 7 for (int i = 1; i <= m; i++) 8 for (int j = 1; j <= n; j++) 9 if (!obstacleGrid[i - 1][j - 1]) 10 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; 11 return dp[m][n]; 12 } 13 };
Well, the code is accepted but it has some obvious redundancy. There are two major concerns:
- Each time when we update
path[i][j]
, we only needpath[i - 1][j]
(at the same column) andpath[i][j - 1]
(at the left column), so it is unnecessary to maintain the fullm*n
matrix. Maintaining two columns is enough. - There are some cases that the loop can be terminated earlier. Suppose
obstacleGrid = [[0, 1, 0, 0], [0, 1, 0, 0], [0, 1, 0, 0]]
, then we can see that it is impossible to reach the bottom-right corner after updating the second column since the number of paths to reach each element in the second column is0
.
Taken these into considerations, we write down the following optimized code.
1 class Solution { 2 public: 3 int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { 4 int m = obstacleGrid.size(); 5 int n = obstacleGrid[0].size(); 6 vector<int> pre(m, 0); 7 vector<int> cur(m, 0); 8 for (int i = 0; i < m; i++) { 9 if (!obstacleGrid[i][0]) 10 pre[i] = 1; 11 else break; 12 } 13 for (int j = 1; j < n; j++) { 14 bool flag = false; 15 if (!obstacleGrid[0][j]) { 16 cur[0] = pre[0]; 17 if (cur[0]) flag = true; 18 } 19 else cur[0] = 0; 20 for (int i = 1; i < m; i++) { 21 if (!obstacleGrid[i][j]) { 22 cur[i] = cur[i - 1] + pre[i]; 23 if (cur[i]) flag = true; 24 } 25 else cur[i] = 0; 26 } 27 if (!flag) return 0; 28 swap(pre, cur); 29 } 30 return pre[m - 1]; 31 } 32 };
Further inspecting the above code, keeping two vectors only serve for the purpose of recoveringpre[i]
, which is simply cur[i]
before its update. So we can use only one vector and the space is further optimized.
1 class Solution { 2 public: 3 int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { 4 int m = obstacleGrid.size(); 5 int n = obstacleGrid[0].size(); 6 vector<int> cur(m, 0); 7 for (int i = 0; i < m; i++) { 8 if (!obstacleGrid[i][0]) 9 cur[i] = 1; 10 else break; 11 } 12 for (int j = 1; j < n; j++) { 13 bool flag = false; 14 if (obstacleGrid[0][j]) 15 cur[0] = 0; 16 else flag = true; 17 for (int i = 1; i < m; i++) { 18 if (!obstacleGrid[i][j]) { 19 cur[i] += cur[i - 1]; 20 if (cur[i]) flag = true; 21 } 22 else cur[i] = 0; 23 } 24 if (!flag) return 0; 25 } 26 return cur[m - 1]; 27 } 28 };