unique_path_ii.png
unique_path_ii_2.png
/**
* Abstract: A DP problem, immediately from the problem specs;
* State relation formulation can be contrieved by thinking about how you might get to position [m][n],
* taking into account the positions right above&to the left of it.
*/
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
int m = obstacleGridSize, n = obstacleGridColSize[0], dp[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (i == 1 || j == 1) {
if (i == 1 && j == 1) {
dp[i][j] = (obstacleGrid[0][0] == 1) ? 0 : 1;
} else if (i != 1) {
dp[i][j] = (obstacleGrid[i - 1][0] == 1) ? 0 : dp[i - 1][j];
} else {
dp[i][j] = (obstacleGrid[0][j - 1] == 1) ? 0 : dp[i][j - 1];
}
} else {
dp[i][j] = (obstacleGrid[i - 1][j - 1] == 1) ? 0 : (dp[i - 1][j] + dp[i][j - 1]);
}
}
}
return dp[m][n];
}
