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

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

今天我们继续学习动态规划当中的网格图模型。

LeetCode 931. 下降路径最小和

思路

题目中已经提到，下降路径可以从这一行当中的任何一个元素开始，也就意味着在一条路径上，某一行的某个元素的上一个元素是它正上方、左上方、右上方某个元素。根据这条性质，我们使用二维数组dp表示(i, j)这个位置的子路径和，据此我们可以写出状态转移方程：dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1]) + matrix[i][j]。注意处理边界情况，也就是元素位于左边界和右边界时，左上方或右上方的元素取不到，因为如果取到的话数组就越界了。

最后取最后一行的最小值，就是最终答案。

Golang 代码

func minFallingPathSum(matrix [][]int) int {m, n := len(matrix), len(matrix[0])dp := make([][]int, m)for i := 0; i < m; i ++ {dp[i] = make([]int, n)}for i := 0; i < n; i ++ {dp[0][i] = matrix[0][i]}for i := 1; i < m; i ++ {for j := 0; j < n; j ++ {if j == 0 {dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j]} else if j == n - 1 {dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + matrix[i][j]} else {dp[i][j] = min(dp[i - 1][j -  1], dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j]}}}return slices.Min(dp[m - 1])
}

LeetCode 2684. 矩阵中移动的最大次数

思路

这道题可以使用 DFS 或 BFS 来解决，也可以使用 DP 来解决。 具体来说，最开始我们可以从矩阵第一列的任何位置开始移动，每次只能移动到右、右上、右下三个位置，且移动到的位置需要满足那个位置的元素大于当前位置的元素。通过观察不难发现，能够在矩阵中移动的最大次数等于矩阵的总列数，也就是说，最大次数对应的移动方案就是从第一列移动到最后一列。

如果我们使用 DP，那么可以使用一个二维的数组dp来记录元素(i, j)，是否是「可到达的」，因此dp保存的是 bool 值。初始状态下，第一列的所有元素都是可以到达的，所以我们令第一列的 bool 值都为 true。从第二列开始，我们判断每一行的元素是否可到达，判断的依据是当前元素左侧的那一列上是否有满足条件的元素使得从那个元素可以到达当前元素。

由于我们使用 DP 的思路来解题，因此应该反向思考，要到达(i, j)，就需要(i, j - 1)、(i - 1, j - 1)以及(i + 1, j - 1)当中的一个或多个满足grid[ni][nj] < grid[i][j]，这样(i, j)才是可达的。

在遍历某一列的每一行之前，使用一个 bool 值reachable来判断这一列是否可达，如果这一列不可达，那么就没必要继续向右侧的列遍历了，直接返回答案即可。

如果所有列都可达，那么答案就是n - 1，其中n是列数。

Golang 代码

func maxMoves(grid [][]int) int {m, n := len(grid), len(grid[0])dp := make([][]bool, m)for i := 0; i < m; i ++ {dp[i] = make([]bool, n)}// 第一行都是可达的, 对第一行进行初始化for i := 0; i < m; i ++ {dp[i][0] = true}for j := 1; j < n; j ++ {var reachable bool = falsefor i := 0; i < m; i ++ {if dp[i][j - 1] && grid[i][j - 1] < grid[i][j] {dp[i][j] = truereachable = true} else if i >= 1 && dp[i - 1][j - 1] && grid[i - 1][j - 1] < grid[i][j] {dp[i][j] = truereachable = true} else if i <= m - 2 && dp[i + 1][j - 1] && grid[i + 1][j - 1] < grid[i][j] {dp[i][j] = truereachable = true}}if !reachable {return j - 1}}return n - 1
}   

LeetCode 2304. 网格中的最小路径代价

思路

这道题的题目描述非常的复杂，实际上这道题在说的就是从第一行出发，寻找一个到达最后一行的最小代价。最小代价保存在moveCost数组当中，moveCost[i][j]代表的含义就是从值为i的点出发到达下一行第j列的代价。为了更好地理解moveCost，我们以图中值为5的点为例，它在moveCost中的位置就是moveCost[5]，由于它位于第一行，因此从它开始到达第二行的4和0的代价分别是14和3。

讲清楚了问题描述，我们现在就可以开始着手解决问题。仍然使用网格图 DP 的思路来解决当前问题，具体来说，设置一个二维的数组dp，用来记录从「最后一行」开始到达(i, j)位置的最小代价。这里重点强调一下最后一行，因为我们要使用自底向上的思路来解决当前问题，最终的答案是dp[0]这一行的最小值。

dp[i][j]的构成有三部分，第一部分就是从它的下一行某个元素k到达(i, j)的路径代价c，第二部分是从下一行元素已经积累的代价dp[i + 1][k]，第三部分是(i, j)本身的值grid[i][j]。汇总三部分可以得到状态转移方程：dp[i][j] = dp[i + 1][k] + c + grid[i][j]。需要再次强调的是，我们使用自底向上的方式来解决问题，所以答案是自底向上更新的。

Golang 代码

func minPathCost(grid [][]int, moveCost [][]int) int {m, n := len(grid), len(grid[0])dp := make([][]int, m)for i := 0; i < m; i ++ {dp[i] = make([]int, n)}// 自底向上, 因此先初始化最后一行的值dp[m - 1] = grid[m - 1]// 最后的答案是 dp 数组第一行的最小值for i := m - 2; i >= 0; i -- {for j := 0; j < n; j ++ {val := grid[i][j]dp[i][j] = math.MaxIntfor k, c := range moveCost[val] {// moveCost 记录的就是从 (i, j) 出发到达下一行第 k 列的那个位置的代价dp[i][j] = min(dp[i][j], dp[i + 1][k] + c)}dp[i][j] += val // 最后需要加上当前位置的值}}return slices.Min(dp[0])
}

LeetCode 1289. 下降路径最小和 II

思路

这道题目与普通版本的「最小路径下降和」比较相似，较大的变化在于当前(i, j)的和可以与上一行的任意列的值累加，且相邻行所选的列不能重复。

我们使用 DP 来解决问题，使用二维数组dp来记录(i, j)位置的最小路径和。由于该位置可以由上一行除j以外任意位置到达，因此我们使用第三重循环来寻找该行最小的路径和，累加得到答案即可。

最终的答案是最后一行的最小值。

Golang 代码

func minFallingPathSum(grid [][]int) int {m, n := len(grid), len(grid[0])dp := make([][]int, m)for i := 0; i < m; i ++ {dp[i] = make([]int, n)}dp[0] = grid[0]for i := 1; i < m; i ++ {dp[i] = grid[i]for j := 0; j < n; j ++ {var val int = math.MaxIntfor k := 0; k < n; k ++ {if j == k {continue}val = min(val, dp[i - 1][k])}dp[i][j] += val}}return slices.Min(dp[m - 1])
}

LeetCode 3418. 机器人可以获得的最大金币数

思路

使用网格图 DP 来解决该问题。每多一个约束条件，DP 数组就应该增加一个维度。对于本题而言，新增加的约束就是「最多可以感化两个单元格」，也就是「最多有两个单元格可以不选」。我们使用三维数组dp来解决问题。第一个和第二个维度对应的是网格图的维度，而第三个维度对应的是「选/不选」的约束。

对于前两个维度而言，(i, j)位置的答案可以由(i - 1, j)或(i, j - 1)贡献得到。而对于第三个维度，由于题目已经限定「不选」的最大次数是 2，因此dp[i][j][0]指的就是全选的情况，dp[i][j][1]对应的就是有一次不选的情况，dp[i][j][2]对应的是有两次不选的情况。这一部分的状态更新可以详见代码。

Golang 代码

func maximumAmount(coins [][]int) int {m, n := len(coins), len(coins[0])dp := make([][][3]int, m + 1)for i := 0; i <= m; i ++ {dp[i] = make([][3]int, n + 1)}for i := 0; i <= m; i ++ {dp[i][0] = [3]int{math.MinInt / 2, math.MinInt / 2, math.MinInt / 2}}for i := 0; i <= n; i ++ {dp[0][i] = [3]int{math.MinInt / 2, math.MinInt / 2, math.MinInt / 2}}dp[0][1] = [3]int{}for i := 1; i <= m; i ++ {for j := 1; j <= n; j ++ {x := coins[i - 1][j - 1]dp[i][j][0] = max(dp[i - 1][j][0] + x, dp[i][j - 1][0] + x)dp[i][j][1] = max(dp[i - 1][j][1] + x, dp[i][j - 1][1] + x, dp[i - 1][j][0], dp[i][j - 1][0])dp[i][j][2] = max(dp[i - 1][j][2] + x, dp[i][j - 1][2] + x, dp[i - 1][j][1], dp[i][j - 1][1])}}return dp[m][n][2]
}