无情赋值粘贴题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
因为一个障碍物，所要考虑的特殊情况和边界问题多了很多。
首先，如果start和finish就是障碍物，那直接game over
对于正常的遇到障碍的情况，障碍所在格子对应的路径直接设置为0，这样也确保了它对其他格子的路径没有影响。
WA的时候意识到数组越界问题没有考虑全，我之前在写62题时使用的是对第一行所有列赋值为1，同理对第一列所有行。
但此题这样的写法就会存在一个致命的漏洞，如果一个障碍存在于边界上的话，那么它会直接影响后续同一方向上所有的格子，因为剩下的格子也不会到达。
因此哪怕是第一行和第一列，其路径值dp也应该由紧邻的前一个格子的路径决定。
这样的话，为了防止数组越界，所有的dp[i-1][]和dp[][j-1]都要保证dp[0][j]和dp[i][0]已经做过初始化处理；
而第一行和第一列的初始赋值则由上一个格子的dp值决定，遇到同样的dp[i-1]和dp[j-1]情况，i和j的初始值也得从1开始；
同时dp[0][0]首先要赋值为1。
粘一下AC代码
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//如果dp[i][j]==1
//说明是障碍物
//对于其可以向左或者向右的下一个点来说，经过该点的路径为0
//需要理解的是一个可选择方向代表一个可以存在的路径
//每一个格子对应的路径都由之前重叠子问题获得
/*
首先要获取二维数组的行数列数
*/
int m = obstacleGrid.length; //数组的length方法获取时候不需要括号
int n = obstacleGrid[0].length;
if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1)
return 0;
int[][] dp = new int[m][n];
//dp[0][0]经过上面的判断后，可以直接赋值为1
dp[0][0]=1;
//initialize
//这里initialize写法是错的，第一列第一行不能直接初始化为1
// for(int j=0;j<n;j++){
// if(obstacleGrid[0][j]==1) dp[0][j]=0;
// else dp[0][j]=1;
// }
// for(int i=0;i<m;i++){
// if(obstacleGrid[i][0]==1) dp[i][0]=0;
// else dp[i][0]=1;
// }
for(int j=1;j<n;j++){
if(obstacleGrid[0][j]==1) dp[0][j]=0;
//dp结果不可以直接赋值为1， 因为有可能因为这一列有障碍物导致后续列格子的无法通过
else dp[0][j]=dp[0][j-1];
}
for(int i=1;i<m;i++){
if(obstacleGrid[i][0]==1) dp[i][0]=0;
else dp[i][0]=dp[i-1][0];
}
for(int i=1;i<m;i++)
for(int j=1;j<n;j++){
if(obstacleGrid[i][j]==1) dp[i][j]=0;
else{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
