LeetCode 63. Unique Paths II

问题描述

• 地址

问题分析

• LeetCode 62. Unique Paths 的进阶题，只不过多了一个障碍物的概念，多加一个判断即可。

代码实现

• 递归（TLE）

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) {
            return 0;
        }
        return findPaths(obstacleGrid, 0, 0);
    }

    public int findPaths(int[][] obstacleGrid, int i, int j) {
        if (i == obstacleGrid.length || j == obstacleGrid[0].length || obstacleGrid[i][j] == 1) {
            return 0;
        }
        if (i == obstacleGrid.length - 1 && j == obstacleGrid[0].length - 1) {
            return 1;
        }
        return findPaths(obstacleGrid, i + 1, j) + findPaths(obstacleGrid, i, j + 1);
    }

• 动态规划

     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) {
            return 0;
        }
         int row = obstacleGrid.length;
         int col = obstacleGrid[0].length;
        int[][] dp = new int[row][col];
         dp[row - 1][col - 1] = obstacleGrid[row - 1][col - 1] == 1 ? 0 : 1;
         for (int j = col - 2; j >= 0; --j) {
             dp[row - 1][j] = obstacleGrid[row - 1][j] == 1 ? 0 : dp[row - 1][j + 1];
         }
         for (int i = row - 2; i >= 0; --i) {
             dp[i][col - 1] = obstacleGrid[i][col - 1] == 1 ? 0 : dp[i + 1][col - 1];
             for (int j = col - 2; j >= 0; --j) {
                 dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i + 1][j] + dp[i][j + 1];
             }
         }
         return dp[0][0];
     }