【Leetcode 每日一题】63. 不同路径 II

问题背景

给定一个 $m\times n$ 的整数数组 $grid$。一个机器人初始位于 左上角（即 $grid[0][0]$）。机器人尝试移动到 右下角（即 $grid[m-1][n-1]$）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 $1$ 和 $0$ 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 $2\times 10^9$。

数据约束

• $m=obstacleGrid.length$
• $n=obstacleGrid[i].length$
• $1\le m,n\le 100$
• $obstacleGrid[i][j]$ 为 $0$ 或 $1$

解题过程

和以前做过的图相关动态规划题非常类似，自己做的时候先想到的是用方向数组来模拟，把自己绕进去了。

具体实现

递归

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(m - 1, n - 1, obstacleGrid, memo);
    }

    private int dfs(int i, int j, int[][] obstacleGrid, int[][] memo) {
        if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) {
            return 0;
        }
        if (i == 0 && j == 0) {
            return 1;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        return memo[i][j] = dfs(i - 1, j, obstacleGrid, memo) + dfs(i, j - 1, obstacleGrid, memo);
    }
}

递推

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j];
                }
            }
        }
        return dp[m][n];
    }
}
空间优化
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int[] row : obstacleGrid) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 0) {
                    dp[j + 1] += dp[j];
                } else {
                    dp[j + 1] = 0;
                }
            }
        }
        return dp[n];
    }
}