Unique Paths

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?

   LeetCode中的变形题目：Minimum Path Sum ， Unique Paths II(障碍物)

 

   题目意思 ： m x n 矩阵 ，从 00 到 (m-1)(n-1)有多少种走法

   思路 ： 可以先假设3x3的矩阵，用树形图画出对应的可能路线图，00 = 01+10  ， 01 = 02 + 11 ， 02 = 12 =22 ，11 = 12 + 21 ，12 = 22 ，21 =22

   所以 ， 可以知道这个问题的子问题就是 矩阵中 matrix[i][j]到终点的路线。

   得到递推式 ：

   

W(R , D) = W(R + 1 , D) + W(R , D+1) D,R < m - 1 , n -1;
W(R , D) = W(R + 1 , D) D = n - 1
W(R , D) = W(R , D +  1) R = m - 1
 

 

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] matrix = new int[m][n]; // 存放每一个点到终点的路线
        for (int i = m - 1 ; i >= 0 ; i--) {
            for (int j = n - 1 ; j >= 0 ; j--) {
                if ( i == m - 1 && j == n - 1)
                    matrix[i][j] = 1;
                else if (j < n - 1 && i < m - 1 )
                    matrix[i][j] = matrix[i + 1][j] + matrix[i][j + 1];
                else if (j == n - 1)
                    matrix[i][j] = matrix[i + 1][j];
                else 
                    matrix[i][j] = matrix[i][j + 1];
            }
        }
        return matrix[0][0];
    }
}

 DISCUSS 中排列组合方法 ：

    总共  m - 1次 down ，n - 1 right  所以 C(n - 1 + m - 1 , m - 1); 得到了下面的：

 public int uniquePaths(int m, int n) {
   if( m == 1 || n ==1) return 1;
   long count = 1;
   if(m>n){
       for(int i=1; i<=n-1; i++){
           count *= (m + i - 1);
           count /= i;
       }
   }else{
       for(int i=1; i<=m-1; i++){
           count *= (n + i - 1);
           count /= i;
       }
   }
   return (int)count;
}

 

第二种类型 ： 表格中添加障碍物 值为1的不能通过 ：

  思路： 很简单，只要在第一种的动态规划解法中，添加一些判断条件就可以了

 

public class Solution {
    // 添加了障碍物 1的格不能通过 
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1) return 0;
        int[][] matrix = new int[m][n];
        for (int i = m - 1 ; i >= 0 ; i--) {
            for (int j = n - 1 ; j >= 0 ; j--) {
                if(obstacleGrid[i][j] == 1) matrix[i][j] = 0; // 多了这句话
                else if ( i == m - 1 && j == n - 1)
                    matrix[i][j] = 1;
                else if (j < n - 1 && i < m - 1 )
                    matrix[i][j] = matrix[i + 1][j] + matrix[i][j + 1]; //注意这里你不要判断右边或下面的是否为1，因为它们的值反正0 ， 没关系的 
                else if (j == n - 1)
                    matrix[i][j] = matrix[i + 1][j];
                else 
                    matrix[i][j] = matrix[i][j + 1];
            }
        }
        return matrix[0][0];
    }
}