动态规划之网格图模型（一）

动态规划之网格图模型（一）

网格图是二维（乃至多维）DP 的典型应用场景。其基础模型可以归纳为：给定一个二维地图，从地图上的某个起点出发，到达终点有多少种可能方案（或是到达终点的最小代价是多少）。

LeetCode 64. 最小路径和

思路

题目要求我们寻找一个从左上角到右下角的最小代价，所以我们用二维数组dp[i][j]记录从起点出发到达每一个点(i, j)的最小代价，最终dp[m][n]就是答案。由于每次只能向下或向右移动，因此状态转移方程就是：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]。

最重要的是处理边界情况，由于我们要求的是路径的最小代价，因此数组的维度开成(m + 1, n + 1)，第零行和第零列的值设置为math.MaxInt，为了不在左上角进行特判，设置dp[0][1] = 0。

根据以上思路，我们进行编码。

Golang 代码

func minPathSum(grid [][]int) int {
    // 变量声明
    m, n := len(grid), len(grid[0])
    dp := make([][]int, m + 1)
    for i := 0; i <= m; i ++ {
        dp[i] = make([]int, n + 1)
    }

    // 设定初始状态
    for i := 0; i <= m; i ++ {
        dp[i][0] = math.MaxInt
    }
    for j := 0; j <= n; j ++ {
        dp[0][j] = math.MaxInt
    }
    dp[0][1] = 0

    // DP
    for i := 1; i <= m; i ++ {
        for j := 1; j <= n; j ++ {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
        }
    }

    return dp[m][n]
}

LeetCode 62. 不同路径

思路

不同路径与「LeetCode 64. 最小路径和」问题非常的相似。区别主要在于状态转移方程的不同。具体来说，使用二维数组dp来表示可能的状态数。dp[i][j]就是从起点出发到达(i, j)的可能状态数。

由于题目要求目标只能在某一点向下或向右移动，对于(i, j)而言，能够到达这一点只能从(i, j - 1)向右移动或是从(i - 1, j)向下移动，因此状态转移方程可以定义为：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

初始情况的dp[1][1]应该被设置为 1，也就是如果终点与起点重合，那么可能的路径条数就是 1，为了避免处理左上角特判，令dp[0][1] = 1。

Golang 代码

func uniquePaths(m int, n int) int {
    dp := make([][]int, m + 1)
    for i := 0; i <= m; i ++ {
        dp[i] = make([]int, n + 1)
    }
    dp[0][1] = 1
    for i := 1; i <= m; i ++ {
        for j := 1; j <= n; j ++ {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m][n]
}

LeetCode 63. 不同路径 II

思路

本题是「LeetCode 62. 不同路径」的衍生题，在地图当中引入了障碍物，让我们继续求达到右下角的可能路径。

解决这类问题的思路仍然是关注状态转移方程与可能的特殊情况。先说状态转移方程：我们已经知道，在(i, j)这一点，可能的路径只能来自左侧或者上侧，如果左边或上边的一个恰为障碍物，则不需要统计来自于那一格的路径。如果(p, q)为障碍物，我们设置它的dp[p][q] = -1，由此可以得到状态转移方程：dp[i][j] = max(d[i - 1][j], dp[i][j - 1], dp[i - 1][j] + dp[i][j - 1])。

特殊情况仍然在左上角，设置dp[0][1] = 1避免左上角特判。

Golang 代码

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m, n := len(obstacleGrid), len(obstacleGrid[0])
    dp := make([][]int, m + 1)
    for i := 0; i <= m; i ++ {
        dp[i] = make([]int, n + 1)
    }
    dp[0][1] = 1
    for i := 1; i <= m; i ++ {
        for j := 1; j <= n; j ++ {
            if obstacleGrid[i - 1][j - 1] == 1 {
                dp[i][j] = -1
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j] + dp[i][j - 1])
            }
        }
    }
    if dp[m][n] == -1 {
        return 0
    } else {
        return dp[m][n]
    }
}

LeetCode 120. 三角形最小路径和

思路

非常经典的一道 DP 入门题，我比较喜欢采用自底向上的方式解决这道题。

具体来说，首先开一个 DP 数组，DP 数组也是三角形的。之后，直接使用三角形的最后一层来初始化 DP 数组的最后一层，从倒数第二层开始进行 DP，状态转移方程是：dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]。

最后dp[0][0]就是最终答案。

Golang 代码

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    dp := make([][]int, n)
    for i := 1; i <= n; i ++ {
        dp[i - 1] = make([]int, i)
    }
    for i := 0; i < n; i ++ {
        dp[n - 1][i] = triangle[n - 1][i]
    }
    for i := n - 2; i >= 0; i -- {
        for j := 0; j <= i; j ++ {
            dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
        }
    }
    return dp[0][0]
}

LeetCode 3393. 统计异或值为给定值的路径数

思路

这是五道题当中最难的那一道题。具体来说，它是另一个「路径统计」问题的变体，要求我们求出路径上所有数异或和为k的路径数目。因此我们在二维数组的基础上，引入第三个维度，用于记录当前路径的异或和是多少。

针对异或运算，一条特殊的性质是异或可以移项，比如对于x ^ y = k，可以移项变为x = y ^ k，利用这条性质，我们可以构建状态转移方程：dp[i][j][x] = dp[i - 1][j][x ^ grid[i - 1][j - 1]] + dp[i][j - 1][x ^ grid[i - 1][j - 1]]。

需要重点关注的问题是，上式中x的含义是什么？针对异或运算，很明显异或的最大值就是grid数组中最大的那个数的二进制位数全为 1 的值，假定这个值为u，如果k不小于u，那么答案就是 0，因为路径上的异或值不可能比异或的最大值还要大。x就是对u从 0 开始进行递增遍历，目的是查看是否有从起点到(i, j)到路径满足异或值为x，最重要搜索的异或值为k。

边界条件仍然在左上角，设置dp[0][1][0] = 1避免特判。

Golang 代码

func countPathsWithXorValue(grid [][]int, k int) int {
    const MOD int = 1e9 + 7
    m, n := len(grid), len(grid[0])
    maxx := 0
    for _, row := range grid {
        maxx = max(maxx, slices.Max(row))
    }
    u := 1 << bits.Len(uint(maxx))  // 求出异或可能的最大值
    if k >= u {
        return 0
    }
    dp := make([][][]int, m + 1)
    for i := 0; i <= m; i ++ {
        dp[i] = make([][]int, n + 1)
        for j := 0; j <= n; j ++ {
            dp[i][j] = make([]int, u)
        }
    }
    dp[0][1][0] = 1
    for i := 1; i <= m; i ++ {
        for j := 1; j <= n; j ++ {
            val := grid[i - 1][j - 1]
            for x := 0; x < u; x ++ {
                dp[i][j][x] = (dp[i - 1][j][x ^ val] + dp[i][j - 1][x ^ val]) % MOD
            }
        }
    }
    return dp[m][n][k] % MOD
}