不同路径

用户7962184

发布于 2020-11-20 06:48:52

27700

代码可运行

运行总次数：0

代码可运行

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？示例：

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

这个也是动态规划，动态规划有个特点，就是从结果去考虑过程，要找到一个最优的某个路径，或者是找出所有的路径，那么他肯定是经过最接近结果的路径，再从那些路径出发，找到开始的地点，比如在这道题里面。终点是右下角，右下角有多少种走法，就是依赖上方的走法加上左方的走法。然后把这个概念推到全图。得出每个点有多少种走法都是这种方式的。从而得出，当前走法 = 左走法+上走法的结论。

至于障碍，如果出现了障碍，说明该点的走法为0。

func main(){
    fmt.Print(uniquePathsWithObstacles([][]int{
        {0,0,0},
        {0,1,0},
        {0,0,0},
    }))
}


func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    if len(obstacleGrid) <= 0 {
        return 0
    }
    row := len(obstacleGrid)
    col := len(obstacleGrid[0])
    //用来动态规划记录上左状态的,上方状态就是当前的状态，滚动数组原理
    runStatus := make([]int, len(obstacleGrid), len(obstacleGrid))
    if obstacleGrid[0][0] != 1 {
        runStatus[0] = 1
    }
    for j := 0; j < col; j++ {
        for i := 0; i < row; i++ {
            if obstacleGrid[i][j] == 1 {
                runStatus[i] = 0
                continue
            }
            if i > 0 && obstacleGrid[i-1][j] == 0 {
                runStatus[i] += runStatus[i-1]
            }
        }
    }
    return runStatus[len(runStatus)-1]
}