Leetcode 不同路径 ||

算法思想（动态规划 - DP）

这道题属于动态规划（Dynamic Programming，DP）问题，核心思想是利用状态转移方程来计算从起点到终点的不同路径数量，同时考虑障碍物的影响。

1. 问题分析

机器人从左上角 (0,0) 只能向右或下移动，目标是到达右下角 (m-1, n-1)。但路径中可能会有障碍物（值为 1 的格子），机器人不能通过这些格子。

我们使用动态规划来记录到达每个位置的路径数，若某个位置有障碍物，则路径数为 0。

2. 状态定义

设 dp[i][j] 表示到达网格 (i, j) 的不同路径数量，则有：

• 如果 grid[i][j] 是障碍物（值为 1），那么 dp[i][j] = 0（因为无法通行）。

• 否则，dp[i][j] 的值等于从左边来的路径数 dp[i][j-1] 加上从上边来的路径数 dp[i-1][j]：

  [
  dp[i][j] = dp[i-1][j] + dp[i][j-1]
  ]

3. 初始化

1. 起点 dp[0][0]：

   • 如果 grid[0][0] 是障碍物，则机器人无法起步，dp[0][0] = 0，直接返回 0。
   • 否则 dp[0][0] = 1，表示机器人只能有一种方式出发。

2. 第一行（只有向右的可能）：

   • 只要当前位置不是障碍物，则 dp[0][j] = dp[0][j-1]。
   • 一旦遇到障碍物，之后的格子都无法到达，设为 0。

3. 第一列（只有向下的可能）：

   • 只要当前位置不是障碍物，则 dp[i][0] = dp[i-1][0]。
   • 同理，遇到障碍物后，后续的 dp[i][0] 设为 0。

4. 状态转移

遍历整个网格：

• 若 grid[i][j] == 1，设 dp[i][j] = 0（无法通行）。
• 否则计算 dp[i][j] = dp[i-1][j] + dp[i][j-1]（来自上方的路径数 + 来自左方的路径数）。

5. 最终结果

dp[m-1][n-1] 存储了到达右下角 (m-1, n-1) 的所有不同路径数，最终返回 dp[m-1][n-1] 作为答案。

6. 复杂度分析

• 时间复杂度： (O(m \times n)) —— 需要遍历整个 m × n 网格一次。
• 空间复杂度： (O(m \times n)) —— 需要 dp 数组存储所有格子的信息（可优化为 O(n)）。

Java solution :

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //首先获取行和列
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        //特殊情况判断，如果起点或终点是障碍物，直接返回 0
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }
        //然后创建dp数组
        int[][] dp = new int[m][n];

        //初始化起点
        dp[0][0] = 1;

        //初始化第一行
        for(int i = 1; i < n; i++) {
            dp[0][i] = (obstacleGrid[0][i] == 1) ? 0 : dp[0][i - 1];
        }
        //初始化第一列
        for(int j = 1; j < m; j++) {
            dp[j][0] = (obstacleGrid[j][0] == 1) ? 0 : dp[j - 1][0];
        }

        //全局更新dp数组
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; 
                }
            }
        }
        
        return dp[m - 1][n - 1];
    }
}