M3742.网格中得分最大的路径

dp, https://leetcode.cn/problems/maximum-path-score-in-a-grid/

给你一个 m x n 的网格 grid，其中每个单元格包含以下值之一：0、1 或 2。另给你一个整数 k。

你从左上角 (0, 0) 出发，目标是到达右下角 (m - 1, n - 1)，只能向右或下移动。

每个单元格根据其值对路径有以下贡献：

值为 0 的单元格：分数增加 0，花费 0。
值为 1 的单元格：分数增加 1，花费 1。
值为 2 的单元格：分数增加 2，花费 1。

返回在总花费不超过 k 的情况下可以获得的 最大分数 ，如果不存在有效路径，则返回 -1。

注意： 如果到达最后一个单元格时总花费超过 k，则该路径无效。

示例 1：

输入： grid = [[0, 1],[2, 0]], k = 1

输出： 2

解释：

最佳路径为：

单元格	`grid[i][j]`	当前分数	累计分数	当前花费	累计花费
(0, 0)	0	0	0	0	0
(1, 0)	2	2	2	1	1
(1, 1)	0	0	2	0	1

因此，可获得的最大分数为 2。

示例 2：

输入： grid = [[0, 1],[1, 2]], k = 1

输出： -1

解释：

不存在在总花费不超过 k 的情况下到达单元格 (1, 1) 的路径，因此答案是 -1。

提示：

1 <= m, n <= 200
0 <= k <= 10^3
grid[0][0] == 0
0 <= grid[i][j] <= 2

动态规划【力扣官方题解】，“带约束的最优路径问题”转化为了一个类似于“三维网格上的背包问题”。

思路与算法

题目要求在总花费不超过 k 的情况下，找到一条从 grid[0][0] 到 grid[m−1][n−1] 的路径，使得获得的分数最大。这种有限制的最优化问题结构类似背包问题，可以用动态规划解决。

定义状态 dp[i][j][c] 表示到达位置 (i,j)，当前花费为 c 时的最大得分。从当前格子向后转移，即从 (i,j) 出发，可以向下或向右移动，将下一个格子的代价和分数加入：

转移方程采用的是“推（Push）”模型：从当前格子推算未来格子。

向下移动到 (i+1, j)：
- 新花费 = c + cost(grid[i+1][j])
- 新分数 = dp[i][j][c] + grid[i+1][j]
- 更新：dp[i+1][j][new_cost] = max(..., new_score)
向右移动到 (i, j+1)：
- 新花费 = c + cost(grid[i][j+1])
- 新分数 = dp[i][j][c] + grid[i][j+1]
- 更新：dp[i][j+1][new_cost] = max(..., new_score)

关于 cost 的定义

cost = 1 (如果 grid != 0)
cost = 0 (如果 grid == 0)

这种“推”式 DP 的好处是：它自然地处理了路径的流向，且通过 if dp[i][j][c] == INF: continue 这种操作，实际上只访问了有效的状态空间，效率比纯暴力三层循环要高。

代码

python

class Solution:
    def maxPathScore(self, grid, k):
        m, n = len(grid), len(grid[0])

        INF = float('-inf')
        dp = [[[INF] * (k + 1) for _ in range(n)] for _ in range(m)]
        dp[0][0][0] = 0

        for i in range(m):
            for j in range(n):
                for c in range(k + 1):
                    if dp[i][j][c] == INF:
                        continue

                    if i + 1 < m:
                        val = grid[i + 1][j]
                        cost = 0 if val == 0 else 1
                        if c + cost <= k:
                            dp[i + 1][j][c + cost] = max(
                                dp[i + 1][j][c + cost],
                                dp[i][j][c] + val
                            )

                    if j + 1 < n:
                        val = grid[i][j + 1]
                        cost = 0 if val == 0 else 1
                        if c + cost <= k:
                            dp[i][j + 1][c + cost] = max(
                                dp[i][j + 1][c + cost],
                                dp[i][j][c] + val
                            )

        ans = max(dp[m - 1][n - 1])
        return -1 if ans < 0 else ans

M3742.网格中得分最大的路径 ​

M3742.网格中得分最大的路径