`

动态规划总结(二)

阅读更多
这篇文章介绍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];
    }
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics