Unique Paths?

leetcode 62

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?

image.png

思路一：

采用动态规划的思路，用数组dp记录到每个格子的不同种走法。可以维护一个二维数组dp，其中dp[i][j]表示到当前位置不同的走法的个数，然后可以得到递推式为: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

var uniquePaths = function(m, n) {
    var dp=[];
    for(var i=0;i<m;i++){
        dp[i]=[];
        for(var j=0;j<n;j++){
            if(i>0 && j>0 ){
               dp[i].push(dp[i][j-1]+dp[i-1][j]);
               }else if(i>0 && j===0){
                   dp[i].push(dp[i-1][j])
               }else if(i===0 && j>0){
                   dp[i].push(dp[i][j-1])
               }else {
                   dp[i].push(1)
               }
        }
    }
      return dp[m-1][n-1];
};

改进：为了节省空间，可以使用以为数组，一位数组存储的时候由于已经存在上一行的走法，只需要再加上前一列的，nice！

  var dp=[];
    for(var i=0;i<n;i++){
        dp.push(1);
    }
    for(var i=1;i<m;i++){
        for(var j=1;j<n;j++){
            dp[j]+=dp[j-1];
        }
    }
    return dp[n-1];

思路二：

实际相当于机器人总共走了m + n - 2步，其中m - 1步向下走，n - 1步向右走，那么总共不同的方法个数就相当于在步数里面m - 1和n - 1中较小的那个数的取法，实际上是一道组合数的问题，写出代码如下:
排列组合从m+n-2个数里去small（m-1和n-1小的那个）
我也不是很明白？问一下？

leetcode 63

ollow 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.
The total number of unique paths is 2.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

思路： 和上一道题一样，判断在这个点里如果等于1的话，就让这个dp[i][j]=0;代表不能从这里走。

var uniquePathsWithObstacles = function(obstacleGrid) {
     var dp=[];
    var m=obstacleGrid.length;
    var n=obstacleGrid[0].length;
    for(var i=0;i<m;i++){
        dp[i]=[];
        for(var j=0;j<n;j++){
            if(obstacleGrid[i][j]==1){
                dp[i].push(0);   
            }else if(i>0 && j>0 ){
               dp[i].push(dp[i][j-1]+dp[i-1][j]);
               }else if(i>0 && j===0){
                   dp[i].push(dp[i-1][j])
               }else if(i===0 && j>0){
                   dp[i].push(dp[i][j-1])
               }else {
                   dp[i].push(1)
               }
        }
    }
      return dp[m-1][n-1];
};

改进：一维数组

var uniquePathsWithObstacles = function(obstacleGrid) {
 var m=obstacleGrid.length;
    var n=obstacleGrid[0].length;
    var dp=[];
    if(obstacleGrid[0][0]===1){
        return 0
    }
    for(var i=0;i<n;i++){
        dp.push(0);
    }
    dp[0]=1;
    for(var i=0;i<m;i++){
        for(var j=0;j<n;j++){
            if(obstacleGrid[i][j]===1){
                dp[j]=0;
            }else if(j>0){
                dp[j]+=dp[j-1]
            }
        }
    }
    return dp[n-1];
};