解答
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if (obstacleGrid[0][0] == 1) {
return 0;
}
if (obstacleGrid[m - 1][n - 1] == 1) {
return 0;
}
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 1, imax = m; i < imax; ++i) {
if (obstacleGrid[i][0] == 1) {
dp[i][0] = 0;
} else {
dp[i][0] = dp[i - 1][0];
}
}
for (int j = 1, jmax = n; j < jmax; ++j) {
if (obstacleGrid[0][j] == 1) {
dp[0][j] = 0;
} else {
dp[0][j] = dp[0][j - 1];
}
}
for (int i = 1, imax = m; i < imax; ++i) {
for (int j = 1, jmax = n; j < jmax; ++j) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
if (obstacleGrid[i - 1][j] == 0) {
dp[i][j] += dp[i - 1][j];
}
if (obstacleGrid[i][j - 1] == 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
}
return dp[m - 1][n - 1];
}
}
要点
本题目充分说明，使用动态规划解题时，初始值很重要。
另外，假如起点和终点均为障碍物的话，可以直接返回，不需要执行后续的求解操作。
准备的用例，如下
@Before
public void before() {
t = new Solution();
}
@Test
public void test001() {
assertEquals(2, t.uniquePathsWithObstacles(new int[][] {
{
0, 0, 0 }, {
0, 1, 0 }, {
0, 0, 0 } }));
}
@Test
public void test002() {
assertEquals(1, t.uniquePathsWithObstacles(new int[][] {
{
0, 1 }, {
0, 0 } }));
}
@Test
public void test003() {
assertEquals(1, t.uniquePathsWithObstacles(new int[][] {
{
0, 0 } }));
}
@Test
public void test004() {
assertEquals(0, t.uniquePathsWithObstacles(new int[][] {
{
0, 0 }, {
1, 1 }, {
0, 0 } }));
}
@Test
public void test005() {
assertEquals(0, t.uniquePathsWithObstacles(new int[][] {
{
0, 0 }, {
0, 1 } }));
}
@Test
public void test006() {
assertEquals(0, t.uniquePathsWithObstacles(new int[][] {
{
1, 0 }, {
0, 0 } }));
}
@Test
public void test007() {
assertEquals(0, t.uniquePathsWithObstacles(
new int[][] {
{
0, 1, 0, 0, 0 }, {
1, 0, 0, 0, 0 }, {
0, 0, 0, 0, 0 }, {
0, 0, 0, 0, 0 } }));
}
