63不同路径II

一题目：

代码&思路：

class Solution {

    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 如果起点 (0, 0) 是障碍物，直接返回 0，因为没有可行的路径
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        // 获取网格的行数
        int m = obstacleGrid.length;
        // 获取网格的列数
        int n = obstacleGrid[0].length;

        // 初始化记忆数组 memory，大小为 (m+1) x (n+1)
        // 多出一行一列是为了方便边界处理，避免额外的条件判断
        int[][] dp = new int[m + 1][n + 1];

        // 初始化起点的路径数量
        // 由于起点 (0, 0) 不是障碍物，我们可以通过设置 memory[0][1] = 1 或 memory[1][0] = 1
        // 来确保 memory[1][1]（即起点）的路径数量为 1
        dp[0][1] = 1;

        // 动态规划填充记忆数组，用i遍历每一行
        for (int i = 1; i <= m; i++) {
            // 遍历每一列
            for (int j = 1; j <= n; j++) {
                // 如果当前格子不是障碍物，计算memory[i][j]的值，如果是障碍物，memory[i][j] 保持默认值 0（不可达）
                if (obstacleGrid[i - 1][j - 1] == 0) {
                    // 当前格子的路径数量 = 上方格子的路径数量 + 左方格子的路径数量
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        // 返回终点的路径数量
        return dp[m][n];
    }
}