62. Unique Paths I and II

Unique Paths I::

https://leetcode.com/problems/unique-paths/description/

解题思路：

1. dp[i][j] = dp[i - 1][j] + dp[i][j-1]

代码如下：
class Solution {
public int uniquePaths(int m, int n) {

    int[][] res = new int[m][n];
    for(int i = 0; i < m; i++)
        res[i][0] = 1;
    for(int i = 0; i < n; i++)
        res[0][i] = 1;
    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            res[i][j] = res[i-1][j] + res[i][j-1];
        }
    }
    return res[m-1][n-1];
}

}

Unique Paths II::

https://leetcode.com/problems/unique-paths-ii/description/
解题思路：

1. 思路跟（1）一样
2. 只是设置当marker = 1时，dp[i][j] == 0

class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {

    int row = obstacleGrid.length;
    int col = obstacleGrid[0].length;
    int[][] dp = new int[row][col];
    for(int i = 0; i < row; i++){
        if(obstacleGrid[i][0] == 1)
            dp[i][0] = 0;
        else{
            if(i==0){
                dp[i][0] = 1;
                continue;
            }
            dp[i][0] = dp[i-1][0];
        }
    }
    for(int i = 0; i < col; i++){
        if(obstacleGrid[0][i] == 1)
            dp[0][i] = 0;
        else{
            if(i==0){
                dp[0][i] = 1;
                continue;
            }
            dp[0][i] = dp[0][i-1];
        }
    }
    for (int i = 1; i < row; i++){
        for(int j = 1; j < col; j++){
            if(obstacleGrid[i][j] == 1)
                dp[i][j] = 0;
            else
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[row-1][col-1];
}

}