动态规划总结(二)

这篇文章介绍unique path等一系列的题目，它们属于二维动态规划的问题，之前一篇文章讲过最长公共子序列(LCS), 最长递增子序列(LIS), 最长非降子序列。有兴趣的可以看一下，这些都是经典的二维动规问题。

1，Unique Paths
给定一个m*n的矩阵，一个机器人在这个矩阵的左上方，它试图走到这个矩阵的右下方，规定机器人只能往右和往下两个方向走，问有多少种不同的路径。

我们把这个矩阵抽象成一个二维数组grid，机器人开始的位置就是grid[0][0]，它可以往下走，也可以往右走，我们初始化数组让它的第0列和第0行的值都1，因为机器人到这些地方只有一条路。对于其它的地方grid[i][j] = grid[i-1][j] + grid[i][j-1]，因为到达(i, j)点必须经过(i, j-1)和(i, j-1)，这样递推式就写出来了。代码如下：

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] result = new int[m][n];
        for(int i = 0; i < m; i++) {
            result[i][0] = 1;
        }
        for(int j = 0; j < n; j ++) {
            result[0][j] = 1;
        }
        
        for(int i = 1; i < m; i++) 
            for(int j = 1; j < n; j++) {
                result[i][j] = result[i-1][j] + result[i][j-1];
            }
        return result[m-1][n-1];
    }
}

2，Unique Paths II
给定一个二维数组，里面的值都是0或1，0代表可以到达，1代表不可以到达。其他规则和上题一样，问有多少种不同的方法。

唯一不同的就是多了障碍物，如果要走到终点，必须要绕过障碍物，换句话说有障碍物的点的值都为0。还要值得注意的是在第0列和第0行中，如果有障碍物，那么障碍物后面的路都是不通的，都要设置为0。代码如下：

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++) {
                if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0;
                else if(i == 0 && j == 0) obstacleGrid[i][j] = 1;
                else if(i == 0) obstacleGrid[0][j] = obstacleGrid[0][j-1];
                else if(j == 0) obstacleGrid[i][0] = obstacleGrid[i-1][0];
                else obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
            }
        return obstacleGrid[m-1][n-1];
    }
}

3，Minimum Path Sum
给定一个m*n的矩阵，里面包含着非负整数，从左上方到右下方，找出最小带权路径。

这是第一题的变形，在初始化第0列的时候 grid[i][0] += grid[i-1][0]; 第0行的初始化为grid[0][i] += grid[0][i-1]; 第(i,j)点的值我们仅需要去一个最小的就可以了，grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j]  （i>=1, j>=1）。代码如下：

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for(int i = 1; i < m; i++) {
            grid[i][0] += grid[i-1][0];
        }
        for(int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i-1];
        }
        
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++) {
                grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
            }
        return grid[m-1][n-1];
    }
}