LeetCode 题解工作台
交替方向的最小路径代价 II
给你两个整数 m 和 n ，分别表示网格的行数和列数。 进入单元格 (i, j) 的成本定义为 (i + 1) * (j + 1) 。 另外给你一个二维整数数组 waitCost ，其中 waitCost[i][j] 定义了在该单元格 等待 的成本。 路径始终从第 1 步进入单元格 (0, 0) 并…
3
题型
0
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个整数 m 和 n，分别表示网格的行数和列数。
进入单元格 (i, j) 的成本定义为 (i + 1) * (j + 1)。
另外给你一个二维整数数组 waitCost，其中 waitCost[i][j] 定义了在该单元格 等待 的成本。
路径始终从第 1 步进入单元格 (0, 0) 并支付入场花费开始。
每一步，你都遵循交替模式：
- 在 奇数秒 ，你必须向 右 或向 下 移动到 相邻 的单元格，并支付其进入成本。
- 在 偶数秒 ，你必须原地 等待恰好 1 秒并在 1 秒期间支付
waitCost[i][j]。
返回到达 (m - 1, n - 1) 所需的 最小 总成本。
示例 1：
输入：m = 1, n = 2, waitCost = [[1,2]]
输出：3
解释：
最佳路径为：
- 从第 1 秒开始在单元格
(0, 0)，进入成本为(0 + 1) * (0 + 1) = 1。 - 第 1 秒：向右移动到单元格
(0, 1)，进入成本为(0 + 1) * (1 + 1) = 2。
因此，总成本为 1 + 2 = 3。
示例 2：
输入：m = 2, n = 2, waitCost = [[3,5],[2,4]]
输出：9
解释：
最佳路径为：
- 从第 1 秒开始在单元格
(0, 0)，进入成本为(0 + 1) * (0 + 1) = 1。 - 第 1 秒：向下移动到单元格
(1, 0)，进入成本为(1 + 1) * (0 + 1) = 2。 - 第 2 秒：在单元格
(1, 0)等待，支付waitCost[1][0] = 2。 - 第 3 秒：向右移动到单元格
(1, 1)，进入成本为(1 + 1) * (1 + 1) = 4。
因此，总成本为 1 + 2 + 2 + 4 = 9。
示例 3：
输入：m = 2, n = 3, waitCost = [[6,1,4],[3,2,5]]
输出：16
解释：
最佳路径为：
- 从第 1 秒开始在单元格
(0, 0)，进入成本为(0 + 1) * (0 + 1) = 1。 - 第 1 秒：向右移动到单元格
(0, 1)，进入成本为(0 + 1) * (1 + 1) = 2。 - 第 2 秒：在单元格
(0, 1)等待，支付waitCost[0][1] = 1。 - 第 3 秒：向下移动到单元格
(1, 1)，进入成本为(1 + 1) * (1 + 1) = 4。 - 第 4 秒：在单元格
(1, 1)等待，支付waitCost[1][1] = 2。 - 第 5 秒：向右移动到单元格
(1, 2)，进入成本为(1 + 1) * (2 + 1) = 6。
因此，总成本为 1 + 2 + 1 + 4 + 2 + 6 = 16。
提示：
1 <= m, n <= 1052 <= m * n <= 105waitCost.length == mwaitCost[0].length == n0 <= waitCost[i][j] <= 105
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate effectively apply dynamic programming to solve grid-based problems?
- question_mark
Does the candidate handle alternating movement correctly and efficiently?
- question_mark
How well does the candidate handle edge cases, like grid boundaries and minimal grid sizes?
常见陷阱
外企场景- error
Failing to alternate directions correctly can lead to suboptimal solutions.
- error
Not accounting for grid boundaries and trying to access out-of-bounds cells.
- error
Overcomplicating the solution by missing the optimal DP approach and using unnecessary nested loops or recursion.
进阶变体
外企场景- arrow_right_alt
What if there are obstacles or restricted cells that cannot be passed?
- arrow_right_alt
How would the solution change if movement was allowed diagonally as well?
- arrow_right_alt
How can this problem be adapted to use a priority queue or greedy approach for pathfinding?