走楼梯——二维有障碍走楼梯（五）

LeetCode_63_UniquePathsII

题目分析：

状态转换方程
  dp[i][j] = 1 == obstacleGrid[i][j] ? 0 : dp[i-1][j] + dp[i][j-1];
  dp[i][j]代表有多少种方法可到达第i行j列
递推初始项
  dp[0][i] = 1 == obstacleGrid[0][i] ? 0 : dp[0][i-1];
  dp[i][0] = 1 == obstacleGrid[i][0] ? 0 : dp[i-1][0];
  
  显然dp[0][0] = 1;不过 1 == obstacleGrid[0][0] 时可直接返回0；
  和前两题一样，第一行从左往右推，第二行从上往下推。
  举例 
  若obstacleGrid为
  {{0, 1, 0},
   {0, 1, 0},
   {0, 0, 0},
   {0, 0, 0}}
  则为dp初始化为
  {{1,0,0},
   {1,0,0},
   {1,0,0}，
   {1,0,0}}

解法一：循环-动态规划

public static int uniquePathsWithObstacles_dp_loop(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int [][]dp = new int[m][n];
    if(1 == obstacleGrid[0][0])
        return 0;
    dp[0][0] = 1;
    for (int i = 1; i < n; ++i)
        dp[0][i] = 1 == obstacleGrid[0][i] ? 0 : dp[0][i-1];

    for (int i = 1; i < m; ++i)
        dp[i][0] = 1 == obstacleGrid[i][0] ? 0 : dp[i-1][0];

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = 1 == obstacleGrid[i][j] ? 0 : dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

解法二：循环-动态规划-递推过程顺带初始化

public static int uniquePathsWithObstacles_dp_loop_lessTime(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;

    int [][]dp = new int[m][n];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if(1 == obstacleGrid[i][j])
                dp[i][j] = 0;
            else if(0 == i && 0 == j)
                dp[i][j] = 1;
            else if(0 == i && 0 < j)
                dp[i][j] = dp[i][j-1];
            else if(0 < i && 0 == j)
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

解法二分析

利用递推步骤的特性和问题划分方式的特点进行的针对性改写，并无普适性，
放在这里的目的，是让大家明白，网上很多解题报告都有类似的优化和改写，不要因此而惧怕或者被迷惑。

解法三：循环-动态规划-内存优化

public static int uniquePathsWithObstacles_dp_loop_lessMemory(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;

    int []dp = new int[n];
    dp[0] = 1;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (obstacleGrid[i][j] == 1) dp[j] = 0;
            else if (j > 0) dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

解法四：循环-动态规划-更进一步内存优化

public static int uniquePathsWithObstacles_dp_loop_bestMemory(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    if(m > n) {
        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (obstacleGrid[i][j] == 1) dp[j] = 0;
                else if (j > 0) dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }else{
        int[] dp = new int[m];
        dp[0] = 1;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[j][i] == 1) dp[j] = 0;
                else if (j > 0) dp[j] += dp[j - 1];
            }
        }
        return dp[m - 1];
    }
}

总结

状态转换方程开始有条件判断了，并且介绍了一些优化改写的技巧，
只为了展示可以这么写而已，动态规划的核心思想依然是那样。

相应例题的 Github