2025-12-14：交替方向的最小路径代价Ⅱ。用go语言，给你一个 m 行 n 列的网格。进入格子 (i, j) 的花费为 (

福大大架构师每日一题

发布于 2025-12-19 10:11:12

750

2025-12-14：交替方向的最小路径代价Ⅱ。用go语言，给你一个 m 行 n 列的网格。进入格子 (i, j) 的花费为 (i+1)*(j+1)。另外每个格子还有一个等待代价矩阵 waitCost，waitCost[i][j] 表示在该格子停留 1 秒钟需要支付的费用。

路径从时间步 1 开始：第一步进入起点 (0,0)，并支付该格子的进入费用。之后时间按秒递增，并且动作必须交替进行：

• 在奇数秒必须向右或向下移动到相邻格子，进入新格子时支付该格子的进入费用；
• 在偶数秒必须在当前格子原地等待恰好 1 秒，并为此支付该格子的 waitCost。

目标是以最小的总费用到达终点 (m-1, n-1)。请计算并返回这个最小总成本。

1 <= m, n <= 100000。

2 <= m * n <= 100000。

waitCost.length == m。

waitCost[0].length == n。

0 <= waitCost[i][j] <= 100000。

输入：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。

题目来自力扣3603。

过程详细描述

1. 初始化起点和终点：
- • 代码首先将起点(0,0)的代价设置为它的进入代价，即(0+1)*(0+1) = 1。这覆盖了输入waitCost矩阵中在(0,0)处的原始值（原为6）。
- • 同时，将终点(m-1,n-1)的代价设置为0，这可能是为了在DP计算中简化终点的处理，因为终点不需要额外的等待代价（但题目中终点需支付进入代价，这里设置0可能是一种调整）。
2. 初始化第一行（i=0）：
- • 对于第一行中的每个单元格(0,j)，其中j从1到n-1，代码计算到达该单元格的最小代价。
- • 代价计算方式为：当前单元格的代价（即waitCost[0][j]的初始值）加上左侧单元格(0,j-1)的累积代价，再加上当前单元格的进入代价j+1（因为i=0，进入代价为1*(j+1)=j+1）。
- • 例如，对于j=1，f[0][1] = f[0][1] + f[0][0] + 1 + 1（初始f[0][1]为1，f[0][0]为1，结果为1+1+1+1=4）。
- • 这一步骤假设路径只能沿着第一行向右移动，代价包括进入每个单元格的费用。
3. 初始化第一列（j=0）：
- • 对于第一列中的每个单元格(i,0)，其中i从1到m-1，代码计算到达该单元格的最小代价。
- • 代价计算方式为：当前单元格的代价（即waitCost[i][0]的初始值）加上上方单元格(i-1,0)的累积代价，再加上当前单元格的进入代价i+1（因为j=0，进入代价为(i+1)*1=i+1）。
- • 例如，对于i=1，f[1][0] = f[1][0] + f[0][0] + 1 + 1（初始f[1][0]为3，f[0][0]为1，结果为3+1+1+1=6）。
- • 这一步骤假设路径只能沿着第一列向下移动，代价包括进入每个单元格的费用。
4. 处理内部单元格（i>=1且j>=1）：
- • 对于其他单元格(i,j)，代码计算到达该单元格的最小代价，考虑从左边单元格(i,j-1)或上边单元格(i-1,j)移动而来。
- • 代价计算方式为：当前单元格的代价（即waitCost[i][j]的初始值）加上左边或上边单元格累积代价的最小值，再加上当前单元格的进入代价(i+1)*(j+1)。
- • 例如，对于单元格(1,1)，计算min(f[1][0], f[0][1]) + (1+1)*(1+1) = min(6,4) + 4 = 4 + 4 = 8，然后加上初始f[1][1]=2，结果为10。
- • 这一步骤假设路径只能向右或向下移动，代价仅包括进入费用，而没有显式处理题目中的等待代价（偶数秒等待）。代码通过DP转移隐含地累积代价，但等待代价未被直接纳入。
5. 返回结果：
- • 经过上述计算后，终点(m-1,n-1)的代价f[m-1][n-1]即为最小总代价。在示例中，f[1][2]最终计算为16。
- • 代码返回该值作为结果。

需要注意的是，题目描述的交替规则（奇数秒移动、偶数秒等待）在代码中并未显式处理。代码实际上实现了一个标准的最小路径和DP，其中每个单元格的代价是进入代价，而等待代价可能通过初始waitCost矩阵的修改被间接包含，但从代码逻辑看，等待代价未被正确集成。输出结果与题目示例匹配的原因可能是DP计算巧合地覆盖了实际代价。

复杂度分析

• 时间复杂度：代码主要包含三个循环：初始化第一行（O(n)）、初始化第一列（O(m)）和处理内部单元格的双重循环（O(mn)）。由于m和n最多为100000，且mn ≤ 100000，整体时间复杂度为O(m*n)，在约束下可行。
• 额外空间复杂度：代码直接修改输入的f矩阵（即waitCost）作为DP表，未使用额外空间（除了少量变量）。因此，额外空间复杂度为O(1)。

总之，代码通过动态规划计算路径代价，但简化了题目规则。实际应用中，如需严格处理交替移动和等待，可能需要更复杂的状态设计。

Go完整代码如下：

package main

import (
    "fmt"
)

func minCost(m, n int, f [][]int)int64 {
    f[0][0] = 1
    f[m-1][n-1] = 0
    for j := 1; j < n; j++ {
        f[0][j] += f[0][j-1] + j + 1
    }
    for i := 1; i < m; i++ {
        f[i][0] += f[i-1][0] + i + 1
        for j := 1; j < n; j++ {
            f[i][j] += min(f[i][j-1], f[i-1][j]) + (i+1)*(j+1)
        }
    }
    returnint64(f[m-1][n-1])
}

func main() {
    m := 2
    n := 3
    waitCost := [][]int{{6, 1, 4}, {3, 2, 5}}
    result := minCost(m, n, waitCost)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def min_cost(m, n, f):
    f[0][0] = 1
    f[m-1][n-1] = 0
    
    for j in range(1, n):
        f[0][j] += f[0][j-1] + j + 1
    
    for i in range(1, m):
        f[i][0] += f[i-1][0] + i + 1
        for j in range(1, n):
            f[i][j] += min(f[i][j-1], f[i-1][j]) + (i+1)*(j+1)
    
    return f[m-1][n-1]

# 测试
if __name__ == "__main__":
    m, n = 2, 3
    wait_cost = [[6, 1, 4], [3, 2, 5]]
    print(min_cost(m, n, wait_cost))  # 输出结果

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCost(int m, int n, vector<vector<int>>& f) {
    f[0][0] = 1;
    f[m-1][n-1] = 0;

    for (int j = 1; j < n; j++)
        f[0][j] += f[0][j-1] + j + 1;

    for (int i = 1; i < m; i++) {
        f[i][0] += f[i-1][0] + i + 1;
        for (int j = 1; j < n; j++)
            f[i][j] += min(f[i][j-1], f[i-1][j]) + (i+1)*(j+1);
    }

    return f[m-1][n-1];
}

int main() {
    vector<vector<int>> waitCost = {{6, 1, 4}, {3, 2, 5}};
    cout << minCost(2, 3, waitCost) << endl;
    return0;
}