Problem:
Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.
Idea:
Dynamic Programming
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int n = obstacleGrid.size(); if (n == 0) return 0; int m = obstacleGrid[0].size(); // f[i][j] = paths(i, j) // INT_MIN -> not solved yet, solution unknown f_ = vector<vector<int>>(n + 1, vector<int>(m + 1, INT_MIN)); return paths(m, n, obstacleGrid); } private: vector<vector<int>> f_; int paths(int x, int y, const vector<vector<int>>& o) { // Out of bound, return 0. if (x <= 0 || y <= 0) return 0; // Reaching the starting point. // Note, there might be an obstacle here as well. if (x == 1 && y == 1) return 1 - o[0][0]; // Already solved, return the answer. if (f_[y][x] != INT_MIN) return f_[y][x]; // There is an obstacle on current block, no path if (o[y - 1][x - 1] == 1) { f_[y][x] = 0; } else { // Recursively find paths. f_[y][x] = paths(x - 1, y, o) + paths(x, y - 1, o); } // Return the memorized answer. return f_[y][x]; } }; |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment