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?
這是一個典型的DP問題
假設只有一個格：

走法是1
++
2:1
+++
3:1
++
++
4個排成方形就是2種
+++
+++
+++
這樣的就是：
1,1,1
1,2,3
1,3,6
所以除了橫著第一排和豎著第一排都是1種，其他的都是上邊和左邊的格的步數(shù)相加

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

Unique Paths II

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.
和上面一樣的思路，遇到有阻礙的點，這個格子可能的路線數(shù)就置0祖屏，需要注意的是第一排和第一列痰娱，只要前面或上面有0婚脱，這個格子也是0叨叙。其余格子還是將左邊的和上邊的數(shù)加起來就好。

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

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
這道題和上面的思想很相似

var minPathSum = function(grid) {
    var row = grid.length;
    var col = row===0 ? 0 : grid[0].length;
    for (var i = 0;i < row;i++) {
        if (i!==0)
            grid[i][0] = grid[i-1][0]+grid[i][0];
        for (var j = 1;j < col;j++) {
            if (i===0)
                grid[0][j] = grid[0][j-1]+grid[0][j];
            else
                grid[i][j] = Math.min(grid[i][j-1],grid[i-1][j]) + grid[i][j];
        }
    }
    return grid[row-1][col-1];
};