63. 不同路径 II

63. 不同路径 II

网格中的障碍物和空位置分别用 1 和 0 来表示。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

动态规划三大步骤:

1. 定义dp数组的含义 == dp = make([][]int, m)
2. 初始化dp数组 == dp[i] = make([]int, n)
3. 计算dp某个状态和前一个状态之间的关系

//1， 普通版本 == 定义边界+ 函数关系式，时空都O(mn)
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m, n := len(obstacleGrid), len(obstacleGrid[0])
    dp := make([][]int, m)          //1，定义dp数组の含义，第ij点有多少路径
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)      //2，初始化dp数组
    }
    if obstacleGrid[0][0] != 1 {    //边界判断：如果起点不是障碍物，置为1，dp开始
        dp[0][0] = 1
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if obstacleGrid[i][j] == 1 {    //当前点上有障碍物，位于障碍物位置的dp的值保持不变
                continue
            }
            if i > 0 {
                dp[i][j] += dp[i-1][j]      //当前点左侧有空白点
            }
            if j > 0 {
                dp[i][j] += dp[i][j-1]      //同上，上方的空白点
            }
        }
    }
    return dp[m-1][n-1]
}

//也是二维 代码写的比较简洁
func uniquePathsWithObstacles(obstacleGrid [][]int) int {   
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])
    dp := make([][]int, m)                     //1，定义dp数组の含义，第ij点有多少路径

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dp[i] == nil {
                dp[i] = make([]int, n)        //2，初始化dp数组
            }
            dp[i][j] = 1
        }
    }

    if obstacleGrid[0][0] == 1 {
        return 0                            //边界判断  检查起点障碍物
    }

    for i := 1; i < m; i++ {                //当前点左侧是障碍物，或者上一个是障碍物
        if obstacleGrid[i][0] == 1 || dp[i-1][0] == 0 {
            dp[i][0] = 0
        }
    }
    for j := 1; j < n; j++ {                //当前点上侧是障碍物，或者上一个是障碍物    
        if obstacleGrid[0][j] == 1 || dp[0][j-1] == 0 {
            dp[0][j] = 0
        }
    }

    for i := 1; i < m; i++ {
        for 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]
}