路径问题1（无障碍）
1、题目：力扣原题
2、问题分析：
根据题目分析，我们可以发现在网格中的任意位置(i,j)只能由其上一个状态（i,j-1）向右或者(i-1,j)向下移动得到。换句话说，当前状态存在的数目可以由上一个状态推导而来，所以可以动态规划来计算。
采用动态规划五部曲的前四部，我们可以如下分析：
1）确定dp数组及含义
dp[i][j]表示从左上角起点到位置（i,j）可以走通的路径数目 ；
2）确定递推公式
因为机器人只可以向右或者向左移动，所以假设某一个位置(i,j)可以由上一个状态（i,j-1）向右或者(i-1,j)向下移动得到：dp[i][j] = dp[i][j-1] + dp[i-1][j]
3)初始化
dp[i][0] = 1,因为从（0,0）到（i,0）的路径只有一条；
dp[0][j]=1,因为从（0,0）到（0，j）的路径也只有一条；
4）确定遍历顺序
根据递推公式，我们可以发现当前位置的结果是从其上方和左方递推得来的，所以遍历顺序可以从左到右层层遍历，从而保证当递推到dp[i][j]时，dp[i][j-1] 和 dp[i-1][j]已经有结果了。
3、代码分析：
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
//初始化
for(int i=0;i
-------------------------------------------------------------------------------------------------------------------------------
路径问题2（有网格障碍）
1、原题：力扣原题
2、问题分析：
根据题目描述，我们可以发现，存在两种变动：
1）若障碍物存在于网格的边缘，那么会影响初始化
若（i,0）存在障碍，那么障碍之后（包括障碍）都是走不到的位置，所以障碍之后的dp[i][0]初始化为0
若（0,j）存在障碍，那么障碍之后（包括障碍）都是走不到的位置，所以障碍之后的dp[0][j]初始化为0
2）若某一个位置（i,j）存在障碍，那么dp[i][j]=0,因为该位置被阻断了，从前面传到位置(i,j)的路径数传不不到终点，那么位置(i,j)参与后面可以走通路径的统计时，dp[i][j]的值为0；
DP五步曲前四步分析如下：
1）dp数组的定义
dp[i][j]表示走到网格位置(i,j)存在的不同路径数
2）递推公式
和问题1一致，某一个位置的只能由其左边和上边推导得到，所以dp公式为：
dp[i][j] = dp[i][j-1] + dp[i-1][j]
3）初始化
从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1，dp[0][j]也同理。
但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。
4）遍历顺序
根据递推公式，从前往后，一层层遍历即可
3、代码分析：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// 初始化
// 因为从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1，dp[0][j]也同理。
// 但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。
int n = obstacleGrid.length, m = obstacleGrid[0].length;
int[][] dp = new int[n][m];
dp[0][0] = 1 - obstacleGrid[0][0];
for (int i = 1; i < m; i++) {
if (obstacleGrid[0][i] == 0 && dp[0][i - 1] == 1) {
dp[0][i] = 1;
}
}
for (int i = 1; i < n; i++) {
if (obstacleGrid[i][0] == 0 && dp[i - 1][0] == 1) {
dp[i][0] = 1;
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (obstacleGrid[i][j] == 1) continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[n - 1][m - 1];
}
}
