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

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. 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(m n)）。由于m和n最多为100000，且m n ≤ 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++完整代码如下：

  

  

  

using namespace std;


 int minCost(int m, int n, 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 
 
 int 
 >> waitCost = {{ 
 6 
 ,  
 1 
 ,  
 4 
 }, { 
 3 
 ,  
 2 
 ,  
 5 
 }}; 
 
 
     cout << minCost( 
 2 
 ,  
 3 
 , waitCost) << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。