机器人数值问题描述

问题描述
在一个二维数组迷宫中，机器人从左上角出发，每次只能向右或者向下；判断是否能到达最右下角；若可以，返回其中一条可行的路径。
网格中的障碍物和空位置分别用 1 和 0 来表示。

动态规划思考
dp[][] 数组的含义：该点可不可达。
转移方程的思考：

对于第一行与第一列：只要自己没有障碍物，就认为可达，同时如果有，直接break跳出，因为这两条特殊的路径 只能由前一个点走到，如果某个点有障碍物，后面的所有点也不可达了。
其他格子 只需要其上 或 其右 有一个格子能到达，同时自己又没有障碍物，就可以达。
路径结果输出：我们从结果倒推到原点。打印一条路径。（为什么是从后往前？ 因为 如果从出发点往后，我们并不能确保当前可达的点最终能不能到达终点，得考虑更多，所以我们从终点向前推，因为起点是一定可以到达的）

public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
int row = obstacleGrid.length;
int column = obstacle[0].length;
boolean[][] dp = new int[row][column];
List<List<integer>> res = new ArrayList<>();

//如果迷宫为空，那么返回值就为空
if(obstacleGrid == null) return null;

//如果起点和终点有障碍物，那是不可达的
if(obstacleGrid[0][0] == 1 || obstacleGrid[0][0] = 1)
    return res;

dp[0][0] = true;
//第一行
for(int i=1;i<column;i++){
    if(obstacleGrid[0][i] == 0){
        dp[0][i] = true;
    }else{
        break;
    }
}
//第一列
for(int i=1;i<row;i++){
    if(obstacleGrid[i][0] == 0){
        dp[i][0] = true;
    }else{
        break;
    }
}
//其余格子
for(int i=1;i<row;i++)
    for(int j=1;j<column;j++){
        //上边或者左右有一个可达 同时 自己又不存在障碍物，就可达
        if( (dp[i-1][j] || dp[i][j-1]) && obstacleGrid[i][j]==0){
            dp[i][j] = true;
        }
    }
//从终点进行反推
int x = row-1;
int y = column-1;
while(x!=0 || y!=0）{   //
    if(x-1>0 && dp[x-1][y]){
        x = x-1;
    }else if(y-1>0 && dp[x][y-1]{   //这个地方用else if，因为其上点 和其右点 选择一个，因为只需要找到一条路径
        y = y-1;
    }
    res.add( Arrays.asList(x,y));
}
Collections.reverse(res);
return res;

}