## 题目描述 给你两个整数 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 <= 105 2 <= m * n <= 105 waitCost.length == m waitCost[0].length == n 0 <= waitCost[i][j] <= 105 ## LeetCode 链接 https://leetcode.cn/problems/minimum-cost-path-with-alternating-directions-ii/