回顾java数组部分知识
int[][]m=new int[2][3] 表达的含义是,两行，三列。
一、不同路径
首先这个题我们分五步走
1.状态表示（按照经验+题目要求）
一般都是以···为结尾或者以···为起始
这道题我们就以dp[i][j]为他要求的到达结尾有多少条路径
此时你要思考一个东西，有多少条路径，他是怎么来的来考虑第二个状态转移方程。
2.状态转移方程
3.初始化
初始化我们采用相当于取巧的一个方式，采用虚拟节点，我们看到上面的状态转移方程，可能就思考一件事，我们会不会出现越界现象，比如最上面的那几个，无法进行-1操作的。
所以我们用虚拟节点，给你包一下，目的是不让他产生越界，红色的都是虚拟的
但是我们使用虚拟节点是有规则的：
1.虚拟节点里面的值，需要保证后面填表是正确的。
那么来思考一下，怎么虚拟节点的格子怎么处理呢，首先你要清楚一件事情，假如只有起点，也就是1*1，那么是不是只有一种，所以要保证起点是1，那么假如是1*2，1*3，是不是也只有一种走法，就是从起点一直向右走，那么再来想出现2*1，的话是不是起点只能往下走，也就只有一种走法，以此类推，所以只需要保证dp[0][1]=1或者dp[1][0]=1，二者不可都为1啊
2.下标的映射，原先表和这个表的对应关系
4.填表顺序
从上倒下，从左到右，
5.返回值
dp[i][j]
最后代码之前，给大家整一下数组，
double[]mark=new double[5],其中的下表是0，1，2，3，4。
这是对应的完整代码
class Solution { public int uniquePaths(int m, int n) { int [][]dp=new int[m+1][n+1]; dp[0][1]=1; for(int i=1;i<m+1;i++){ for(int j=1;j<n+1;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m][n]; } }
二、不同路径II
这个题也是一样五步走，
1.状态表示（按照经验+题目要求）
一般都是以···为结尾或者以···为起始
这道题我们就以dp[i][j]为他要求的到达结尾有多少条路径
此时你要思考一个东西，有多少条路径，他是怎么来的来考虑第二个状态转移方程。
2.状态转移方程
还是我们的那个dp[i][j]=d[i-1][j]+dp[i][j-1],但是这个题和上一个题有区别，就是这个题多个障碍物，我们该如何处理这个障碍物呢？
我的刚开始做的时候很迷惑，在想这个障碍物改咋整，假如他不是我的终点，但是他又正好在经过终点的路上。其实这是我思维的一个误区，因为我其实已经选定好从结尾开始看了。
从结尾看就两种情况：
1.障碍物在终点处：在终点，肯定就到不了，就是0呗
2.障碍物不在终点：不在终点就是要想，他正常是左边的+上面的，遇到障碍物就和上面一样，视为0即可
3初始化：和上面一样。
4.填表顺序
从上倒下，从左到右，
5.返回值
dp[i][j]
这里在引入一个小知识
(int[][] ob) {
int m=ob.length,n=ob[0].length;
当二维数组的时候，m表示二维数组的列，n表示行数
class Solution { public int uniquePathsWithObstacles(int[][] ob) { int m=ob.length,n=ob[0].length; int[][]dp=new int[m+1][n+1]; dp[0][1]=1; for(int i=1;i<m+1;i++){ for(int j=1;j<n+1;j++){ //这里容易产生一个误区，考虑原来数组是0的部分，我刚开始是考虑1的所以导致想不明白假如我是1，我给障碍物赋值为0，问题障碍物本身就0。 //然后看一眼题解，发现是把没有石头的部分，去那么算 if(ob[i-1][j-1]==0){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } } return dp[m][n]; } }
class Solution { public int uniquePathsWithObstacles(int[][] ob) { int m=ob.length,n=ob[0].length; int[][]dp=new int[m+1][n+1]; dp[0][1]=1; for(int i=1;i<m+1;i++){ for(int j=1;j<n+1;j++){ if(ob[i-1][j-1]==1){ //我按照我的想法来一遍，发现不是误区，其实也是对的，只是说，这个需要赋值为0（不写赋值也可）之后，就要跳到下一个，不然的话，他就相当于没有障碍物了 dp[i][j]=0; continue; } dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m][n]; } }
