62、63 不同路径

62. 不同路径

题目求start -> finish的路径总数。因为只能向下或者向右，所以很显然例题中start(0,0) -> (0,6) 只有一种可能，那就是一直往右。
同理，(0,0) -> 第一行的任何一个位置都只有一种情况。

// nums[3][7] 记录 start -> 任意位置的路径数
for(int i=0;i<m;i++){
    nums[0][i] = 1; 
}

同理，start(0,0) -> (2,6) 只有一种可能，那就是一直往下。
同理，(0,0) -> 第一列的任何一个位置都只有一种情况。

 for(int i=0;i<n;i++){
     nums[i][0] = 1;
 }

我们把 (0,0) -> 到任何一个位置的路径数标到方格上，即：

因为只能向下或者向右，那么 start -> (1,1) 的路径总数有：
(0,0) -> (0,1) ->(1,1)
(0,0) -> (1,0) ->(1,1)
也就是count( (1,0) ) + count( (0,1) ) = 1+1 =2
所以剩下的空格便可以通过上边和左边推出。

 for(int i=0;i<m;i++){
     for(int j=0;j<n;j++){
         if(i==0 || j==0) continue;
         nums[i][j] = nums[i][j-1] + nums[i-1][j];
     }
 }

那么，答案便是 finial（2，6）位置对应的值。

解法一：

// 完整代码
class Solution {
    public int uniquePaths(int m, int n) {
    	// nums[3][7] 记录 start -> 任意位置的路径数
        int[][] nums = new int[m][n];
        for(int i=0;i<m;i++){
            nums[i][0] = 1; 
        }
        for(int i=0;i<n;i++){
            nums[0][i] = 1;
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 || j==0) continue;
                nums[i][j] = nums[i][j-1] + nums[i-1][j];
            }
        }
        return nums[m-1][n-1];
    }
}

解法二：

根据：nums[i][j] = nums[i][j-1] + nums[i-1][j]可以得知nums[i][j] 是由（上一行和本行的）旧数据推导而出，并且我们最终只需要finial 位置的路径数，无需其他旧数据。
所以可以简化空间，将int[m][n]优化为int[n]。
所以：

class Solution {
    public int uniquePaths(int m, int n) {
        int[] nums = new int[n];
        // 初始第一行均为1
        Arrays.fill(nums,1);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 || j==0) continue;
                nums[j] += nums[j-1];
            }
        }
        return nums[n-1];
    }
}

63. 不同路径 II

相较于上一题，多了障碍物
所以：
第一行：如果不出现障碍物均为1，出现障碍物的话障碍物前为1 其他为0（因为无法到达）

for(int i=0; i<m; i++){
    if(obstacleGrid[0][i] == 1) break;
    nums[0][i] = 1;
}

第一列：如果不出现障碍物均为1，出现障碍物的话障碍物前为1 其他为0（因为无法到达）

for(int i=0; i<m; i++){
    if(obstacleGrid[i][0] == 1) break;
    nums[i][0] = 1;
}

其他空格：如果本位置不出现障碍物nums[i][j] = nums[i][j-1] + nums[i-1][j]，如果出现障碍物的话为0

for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
        if(i==0 || j==0) continue;
        if(obstacleGrid[i][j] == 0){
            nums[i][j] = nums[i-1][j] + nums[i][j-1];
        }
    }
}

解法一：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] nums = new int[m][n];
        for(int i=0; i<m; i++){
            if(obstacleGrid[i][0] == 1) break;
            nums[i][0] = 1;
        }
        for(int i=0; i<n; i++){
            if(obstacleGrid[0][i] == 1) break;
            nums[0][i] = 1;
        }

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 || j==0) continue;
                
                if(obstacleGrid[i][j] == 0){
                    nums[i][j] = nums[i-1][j] + nums[i][j-1];
                }
            }
        }
        return nums[m-1][n-1];
    }
}

解法二：

同样可以得到：
根据nums[i][j] = nums[i][j-1] + nums[i-1][j]可以得知nums[i][j] 是由（上一行和本行的）旧数据推导而出，并且我们最终只需要finial 位置的路径数，无需其他旧数据。
所以可以简化空间，将int[m][n]优化为int[n]。
所以：

/**
解法二：压缩数组
由解法一   “nums[i][j] = nums[i][j-1] + nums[i-1][j];如若出现障碍物即为0” 得旧数据仅仅用于下一行的累加，即旧数据没有被存储的必要。可以简化为一维数组，即 nums[j] += nums[j-1]; 如若出现障碍物即为0。
需要注意的是nums[0]的值，即当（obstacleGrid）第一列若某元素出现障碍物，之后的元素便都为0了，所以需要额外判断nums[0]
**/

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] nums = new int[n];
        for(int j=0; j<n; j++){
            if(obstacleGrid[0][j] == 1) break;
            nums[j] = 1;
        }
        
        nums[0] = 1;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                // 需要额外判断nums[0]
                if(nums[0] == 1){
                    if(j==0 && obstacleGrid[i][j] == 1){
                        nums[0] = 0;
                    }
                }
                if(i==0 || j==0) continue;

                if(obstacleGrid[i][j] == 0){
                    nums[j] += nums[j-1];
                }else{
                    nums[j] = 0;
                }
            }
        }
        return nums[n-1];
    }
}