Leetcode 62.不同路径 & 63.不同路径II

问题描述

62.不同路径

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

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

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

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下

2. 向右 -> 向下 -> 向右

3. 向下 -> 向右 -> 向右 示例 2:

输入: m = 7, n = 3 输出: 28

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-paths

 

63.不同路径II

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

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右 -> 向右

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-paths-ii

 

思路:

动态规划:

dp[ i ] [ j ]表示在格子位置ij处到达终点有几条路径

从终点开始,通过O(n*m)的循环构建dp数组,最后返回dp[0][0]

空间复杂度为O(m*n)

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

 

减小空间复杂度的方法

1、按行扫描时发现只要使用当前访问位置的上一行的值和刚刚修改过的值。所以只要保存两排长度为n的数组（dp和pre）即可。空间复杂度为O（2*n）

2、进一步减小，使用一维长度为n的数组dp[]。我们发现在更改dp[i]之前，dp[i-1]是它的下一行，dp[i]当前值为它的右侧。

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

有障碍物的情况：只要在遍历到有障碍物的格子时，把它到终点的路径条数置为0即可。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        return uniquePaths(m,n,obstacleGrid);
    }
    
    public int uniquePaths(int m, int n,int[][] obstacleGrid) {
        int[] dp=new int[n+1];
        dp[n-1]=1;
        for (int i=m-1;i>=0;i--){
            for (int j=n-1;j>=0;j--){
                if(obstacleGrid[i][j]==1){
                    dp[j]=0;
                    continue;
                }
                dp[j]=dp[j]+dp[j+1];
            }
        }
        return dp[0];
    }
​
}