不同路径 II

题目链接

不同路径 II

题目描述

注意点

• obstacleGrid[i][j] 为 0 或 1
• 1 <= obstacleGrid.length, obstacleGrid[i].length<= 100

解答思路

• 可以使用动态规划解决本题，到达任意一个位置[i][j]可能是由[i - 1][j]向下移动也可能是由[i][j - 1]向右移动，所以从起点开始，由其上方和左方的点的路径数量推出到达当前点的路径数量，并保存到达当前点的路径数量（方便继续推出其他点的路径数量），直到到达终点为止

代码

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 起点障碍物
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 障碍物无法到达
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }
                if (i > 0) {
                    dp[i][j] += dp[i - 1][j];
                }
                if (j > 0) {
                    dp[i][j] += dp[i][j - 1];
                }
            }
        }
        return dp[row - 1][col - 1];
    }
}

关键点

• 动态规划的思想
• 注意边界问题
• 注意起点就是障碍物的特殊情况