动态规划（二）

上一篇文章对于动态规划做了一个简单的介绍，这一次，我想来讲讲动态规划中，不同路径这一类型的题目。这种类型的题目这Leetcode中也有，分别是：
第62题：不同路径 https://leetcode-cn.com/problems/unique-paths/
第63题：不同路径2 https://leetcode-cn.com/problems/unique-paths-ii/
首先我们来看第62题，题目如下：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

image.png
看到这个问题我们就可以有一个分治的思想。要求到网格右下角的路径数量，我们只需要求到达右下角左边的这个格子的路径数量加上右下角上边的这个格子的路径数量即可。按照这样的思想，我们就可以依次往上递推，直到起点。ok，那我们就可以采用动态规划来求解了，状态转移方程是dp[i][j] = dp[i-1][j] + dp[i][j-1]，当i=0或者是j=0的时候，那就是在最上面那一行和最左边那一行。很明显，这两行的路径数量只能是1，其余的值按照状态转移方程填满就可以啦，代码如下：

public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

但其实上面的代码还有优化的空间因为，我们每次只需要 dp[i-1][j],dp[i][j-1]所以我们只要记录这两个数，我们可以使用滚动数组的思想，把空间复杂度降到O(n)。cur[j - 1]代表着原来的dp[i][j-1]，而cur[j]就代表着dp[i-1][j]，因为cur[j]存着的是上一次循环到这一列的值。代码如下：

public static int uniquePaths(int m, int n) {
        int[] cur = new int[n];
        Arrays.fill(cur, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] += cur[j - 1];
            }
        }
        return cur[n - 1];
    }

---

好了，现在我们来看第63题，题目如下：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

image.png

这一题和上一题唯一存在的区别就在于加了障碍物，这只需要进行一些条件判断即可。代码如下：

public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (m == 0 || n == 0 || obstacleGrid[0][0] == 1) return 0;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < n; i++) {
            dp[0][i] = obstacleGrid[0][i] != 1 && dp[0][i - 1] != 0 ? 1 : 0;
        }
        for (int i = 1; i < m; i++) {
            dp[i][0] = obstacleGrid[i][0] != 1 && dp[i - 1][0] != 0 ? 1 : 0;
        }
        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];
    }

当然，这里也可以用滚动数组来降低时间复杂度，代码如下：

public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (m == 0 || n == 0 || obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] != 1) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }

哎，这个滚动数组的边界我调了好久，还是太菜了。。。
emmmmm，其实LeetCode上还有不同路径3的，但是有点难呀，下次再做吧（一定做，hhhhhhhhhh）

---

好了，以上就是我对于动态规划中不同路径这类题目的一些理解，本人才疏学浅，如有不对，还望批评指正。