0063.不同路径II

0063.不同路径II (opens new window)

解法 ： 动态规划

由于路上有障碍，只是只对数组中标记为0的位置进行判定，其余与上一题相同

java

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int height = obstacleGrid.length, width = obstacleGrid[0].length;
    int[][] judgeArray = new int[height + 1][width + 1];
    judgeArray[0][1] = 1;
    for (int i = 1; i <= height; i++) {
        for (int j = 1; j <= width; j++) {
            if (obstacleGrid[i - 1][j - 1] == 0) {
                judgeArray[i][j] = judgeArray[i - 1][j] + judgeArray[i][j - 1];
            }
        }
    }
    return judgeArray[height][width];
}

go

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	matrix := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		matrix[i] = make([]int, n+1)
	}
	matrix[0][1] = 1
	for i, row := range obstacleGrid {
		for j, cell := range row {
			if cell == 1 {
				continue
			}
			matrix[i+1][j+1] = matrix[i+1][j] + matrix[i][j+1]
		}
	}
	return matrix[m][n]
}