动态规划9-不同路径问题

该问题取自Leetcode 62,63

不同路径I

问题描述

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

问总共有多少条不同的路径?

思路

这个问题我们可以试着来构造一个二维dp数组进行解决,假设是一个5X5的网格,那么就要构造一个5X5的数组

这个数组就是表示走到这一格有多少种走法,比如[1,1]的值,可以想的出来,是等于2,因为有两种走法,向右->向下和向下->向右.我们首先创造出这样一个数组,然后令其所有值都为0

dp
00000
00000
00000
00000
00000

由于题目规定了只能向右或者向下走,所以有一些边界值是可以提前知道的,比如第一排和第一列的值,都是1.

dp
11111
10000
10000
10000
10000

然后就可以开始思考,是怎么样来进行走的,由于我们只能向右或者向下走,那么走到某一格子的走法,就是左边一格,和上边一格的走法的加和,即一个递推公式就出来了
$$
dp[i][j] = dp[i-1][j] + dp[i][j-1]
$$
所以其结果也就可以推出来了.

但是,我们可以留意到,这个递推公式,在每一次求值的时候,只与上边的一个值和之前的一个值有关,那么我们可不可以对其进行优化,令二维数组变为一个一维的数组,具体过程就不再这里解释了,直接看代码就可以了

编码

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

不同路径II

问题描述

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

思路

在这个问题中,我们发现多了一个障碍物的设定,那么可以知道,有障碍的点是不可达的,那么我们就要想一下怎么在dp数组中表示这个不可达的概念,很自然就想到将其设为0,那么当我们遍历的时候,如果左边的点值是0,上边的点值是2,就说明这个点只能从上面的点抵达,走法也同样是2,即0+2=2.

我们还是从没有优化的版本开始说起,我们要怎么样来初始化这个二维数组呢,在上面的第一题中,我们将第一行,第一列都设为了1,但是在这个问题中,我们需要知道,假如第一行中有某一个元素为障碍物的话,其右边的所有结点都是不可达的,同样如果第一列中某个元素为障碍物,其下面所有结点也是不可达的.

初始化进程说完了,那么我们来说说遍历的事,在上上面一段,说了可以用0来表示不可达,所以在每一次遍历时,我们先判断这个点的网格是否为有障碍物的点,如果有,直接设为0,如果没有,那么还是沿用以前的办法将左边和上面的值加起来就可以了.

根据上面的过程,我们可以写出一个没有优化的版本,也就是下面的编码中的第一段代码.

但是跟上面这一题一样,我们也可以做出一个将dp数组优化成一维数组的解法,在初始化进程中,我选择了初始化第一行的时候,用一个标志量,如果遇到了障碍物,则将其设为true,这样后面的值都会被初始化为0,第一列也是类似的,后面的遍历与上面没有优化时基本一致,就不说了.

编码

二维dp

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

一维dp

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        if(n == 0 || m == 0){
            return 0;
        }
        if(obstacleGrid[0][0] == 1 || obstacleGrid[n-1][m-1] == 1){
            return 0;
        }
        int[] dp = new int[m];
        boolean rowBarrier = false;
        for(int i = 0;i<m;i++){
            if(obstacleGrid[0][i]!=0){
                rowBarrier = true;
            }
            dp[i] = rowBarrier?0:1;
        }
        boolean colBarrier = false;
        for(int i = 1;i<n;i++){
            if(obstacleGrid[i][0]!=0){
                colBarrier = true;
            }
            dp[0] = colBarrier?0:1;
            for(int j = 1;j<m;j++){
                dp[j] = obstacleGrid[i][j] == 0 ? dp[j] + dp[j-1] : 0;
            }
        }
        return dp[m-1];
    }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×