LeetCode-62. Unique Paths/63. Unique Paths II

怼烎@ 2022-07-27 11:57 192阅读 0赞

## 62. Unique Paths ##

Problem:

> A robot is located at the top-left corner of a m x n grid (marked  
> ‘Start’ in the diagram below).
> 
> The robot can only move either down or right at any point in time. The  
> robot is trying to reach the bottom-right corner of the grid (marked  
> ‘Finish’ in the diagram below).
> 
> How many possible unique paths are there?

![这里写图片描述][20160412230340887]

> Above is a 3 x 7 grid. How many possible unique paths are there?
> 
> Note: m and n will be at most 100.

Analysis:  
这个题就是简单的DP，经典实现方法有两种，一种递归，一种while循环dp，其中循环dp可以有更节省空间的方法。

Answer:  
递归：

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

while循dp：

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

while循dp改进：

public class Solution {
        public int uniquePaths(int m, int n) {
            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];
        }
    }

--------------------

## 63. Unique Paths II ##

Follow up for "Unique Paths":
    Now consider if some obstacles are added to the grids. How many unique paths would there be?
    An obstacle and empty space is marked as 1 and 0 respectively in the grid.
    For example,
    There is one obstacle in the middle of a 3x3 grid as illustrated below.
    [
      [0,0,0],
      [0,1,0],
      [0,0,0]
    ]
    The total number of unique paths is 2.
    Note: m and n will be at most 100.

Analysis:

*  比上一题加了阻碍条件，所以要做阻碍处理。
 *  注意第0行和第0列。如果没有障碍物，所有路径都是1，但是如果有障碍物。从第一个有障碍物开始，这一排和这一列以后的所有路径是0，就是以后的地方都到不了。
 *  利用flag标记将第一行之后的dp标记为0，并在遍历的时候注意第一列如果有1，则将dp\[0\]=0。

Answer:

public class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            if(obstacleGrid[m-1][n-1]==1) return 0;
            int[] dp = new int[n];
            int flag=0;//第一行为1的位置
            for(int i=0;i<n;i++){
                if(obstacleGrid[0][i]==0) dp[i]=1;
                else{
                    dp[i]=0;
                    flag=i;
                    break;
                }
            }
            //使第一行从1开始后的dp都为0
            if(flag>0){
                for(int i=flag+1;i<n;i++){
                    dp[i]=0;
                }
            }
            for(int i=1;i<m;i++){
                if(obstacleGrid[i][0]==1) dp[0]=0;//解决第一列有1的情况，主要防止类似{
        {0,0},{1,0}}的情况
                for(int j=1;j<n;j++){
                    if(obstacleGrid[i][j]==1) dp[j]=0;//做判断区别
                    else{
                        dp[j]=dp[j-1]+dp[j];
                    }
                }
            }
            return dp[n-1];
        }
    }

[20160412230340887]: /images/20220724/a9a77c83e2d843ab886733cd4b8d65a2.png