The Dynamic Programming DP is one of the most-used approach to solve problems that satisfy the overlapping sub-problems and the optimal substructures. The simplest example is to compute Fibonacci numbers where Fib(n) can be divided into smaller problems of Fib(n-1) and Fib(n-2). The sub problems can be further decomposed.
The solution of subproblems is also part of the solution of the bigger problem, which is called optimal substructures. A few days ago, the DP approach is discussed in this problem, that solves the counting of unique paths. This follow-up problem places a few obstacles in the grid. Of course, when you count the unique paths, you can’t walk through the obstacles.
The original problem description at Leetcode Online Judge can be found in this page, which you can submit your solutions to.
We can still use DP. However, we must ignore the positions that are impossible to come from (either the positions contain obstacles or its previous path contains obstacles).
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 39 40 41 | // https://helloacm.com/cc-coding-exercise-unique-paths-ii-dynamic-programming-with-obstacles-leetcode-online-judge-dp-with-constraints/ class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { /* first position is obstacle */ if (obstacleGrid[0][0] == 1) return 0; int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); /* exit position is obstacle */ if (obstacleGrid[m - 1][n - 1] == 1) return 0; int sol[100][100]; sol[0][0] = 1; /* fill the first row */ for (int i = 1; i < n; i ++) { if (obstacleGrid[0][i] == 1) { sol[0][i] = 0; // it is an obstacle so none paths. } else { sol[0][i] = sol[0][i - 1]; } } /* fill the first column */ for (int i = 1; i < m; i ++) { if (obstacleGrid[i][0] == 1) { sol[i][0] = 0;// it is an obstacle so none paths. } else { sol[i][0] = sol[i - 1][0]; } } for (int i = 1; i < m; i ++) { for (int j = 1; j < n; j ++) { int c = 0; /* the up position is blocked */ if (obstacleGrid[i - 1][j] == 0) c += sol[i - 1][j]; /* the left position is blocked ? */ if (obstacleGrid[i][j - 1] == 0) c += sol[i][j - 1]; sol[i][j] = c; } } return sol[m - 1][n - 1]; } }; |
// https://helloacm.com/cc-coding-exercise-unique-paths-ii-dynamic-programming-with-obstacles-leetcode-online-judge-dp-with-constraints/
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
/* first position is obstacle */
if (obstacleGrid[0][0] == 1) return 0;
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
/* exit position is obstacle */
if (obstacleGrid[m - 1][n - 1] == 1) return 0;
int sol[100][100];
sol[0][0] = 1;
/* fill the first row */
for (int i = 1; i < n; i ++) {
if (obstacleGrid[0][i] == 1) {
sol[0][i] = 0; // it is an obstacle so none paths.
} else {
sol[0][i] = sol[0][i - 1];
}
}
/* fill the first column */
for (int i = 1; i < m; i ++) {
if (obstacleGrid[i][0] == 1) {
sol[i][0] = 0;// it is an obstacle so none paths.
} else {
sol[i][0] = sol[i - 1][0];
}
}
for (int i = 1; i < m; i ++) {
for (int j = 1; j < n; j ++) {
int c = 0;
/* the up position is blocked */
if (obstacleGrid[i - 1][j] == 0) c += sol[i - 1][j];
/* the left position is blocked ? */
if (obstacleGrid[i][j - 1] == 0) c += sol[i][j - 1];
sol[i][j] = c;
}
}
return sol[m - 1][n - 1];
}
};The overall complexity is still O(mn) and the space complexity is O(mn) as well. The difference with Unique Path problem is the added-constraints checks when summing up the sub-optimal paths.
Unlike pure DP problems (such as Unique Path problem), there is no obvious pure mathematics formula (i.e. using combinatorics) to solve the Dynamic Programming with constraints.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: VBScript Function to Run Program at Remote Computer
Next Post: Storing a number inside a string using PHP
