2026-10-26：交替方向的最小路径代价Ⅲ。用go语言，给定两个整数 m、n，表示网格有 m 行、n 列，终点是右下角单元格 (m-1, n-1)。另有一个二维整数数组 penalty。
每个单元格 (i, j) 都有一个进入费用，数值为 (i+1) 乘以 (j+1)。起点是 (0, 0)，出发时先支付起点的进入费用。
从起点进入后，开始计算行动次数，第一次行动编号为 1。每次行动可以选择移动到上下左右相邻的单元格，也可以留在当前单元格不动。行动编号每执行一次就加 1，因此行动编号的奇偶性会不断交替。
移动方向受行动编号奇偶性的约束：编号为奇数时，允许向右或向下移动；编号为偶数时，允许向左或向上移动。
费用规则如下：如果移动方向符合当前行动编号要求的奇偶性，只需支付目标单元格的进入费用。如果移动方向不符合要求，则除了支付目标单元格的进入费用，还要额外支付 penalty[i][j]，其中 (i, j) 是移动前所在的单元格。若选择在当前单元格等待，则需要支付 penalty[i][j]，其中 (i, j) 就是当前所在单元格。
要求计算从 (0, 0) 到达 (m-1, n-1) 所需的最小总费用。
1 <= m, n <= 100000。
2 <= m * n <= 100000。
penalty.length == m。
penalty[i].length == n。
0 <= penalty[i][j] <= 100000。
输入： m = 2, n = 2, penalty = [[5,3],[1,4]]。
输出： 8。
解释：
最优路径为：
从单元格 (0, 0) 开始，入口代价为 (0 + 1) * (0 + 1) = 1。
行动 1：向下移动到单元格 (1, 0)，入口代价为 (1 + 1) * (0 + 1) = 2。
行动 2：向右移动到单元格 (1, 1)，入口代价为 (1 + 1) * (1 + 1) = 4，因为违反了偶数奇偶性规则，额外代价为 penalty[1][0] = 1。
因此，总代价为 1 + 2 + 4 + 1 = 8。
题目来自力扣4003。
一、核心思路：把"行动编号的奇偶性"变成状态的一维
这道题的本质是在网格上求最小代价路径，但它有一个普通最短路没有的约束：能往哪个方向走，取决于"这是第几次行动"。
关键观察有三条：
1.费用只和"位置的序列 + 哪些行动违规"有关，和历史无关。也就是说，站在同一个格子、面对同一个奇偶性的下一步行动时，未来的最优决策完全一样，之前是怎么走过来的不影响。这满足最优子结构，可以用最短路（Dijkstra）。
2.行动编号只需要保留奇偶性。编号 1、3、5… 都是奇数（允许向右/向下），2、4、6… 都是偶数（允许向左/向上）。真正影响费用的只有"下一条行动是奇数还是偶数"这一个 bit。所以不需要把"走了几步"放进状态里，否则状态数会爆炸。
3.每次行动（包括原地等待）都会让编号 +1，也就是奇偶性必然翻转。所以状态里那个 bit 在每次转移后都要取反。
于是原来的"m×n 个格子"被扩展成2·m·n 个状态：(格子 i,j) × (下一条行动编号的奇偶性 k)。整个问题就变成在这张扩展图上跑一次单源最短路。
顺带说明"等待"为什么必须存在：当你想连续两次往右走时，中间那一步（偶数编号）不允许向右，你必须"消耗"掉这次行动——要么原地等待，要么绕路。等待的代价是 penalty[当前格]，绕路的代价是邻格的入口费，二者孰优孰劣正需要算法去比较，所以"原地不动"是一条独立且必要的转移。二、方向数组与奇偶性的对应关系
代码里四个方向按固定顺序排列：上、下、左、右，下标分别是 0、1、2、3。
• 下标 1（下）和 3（右）是奇数 → 对应"奇数编号允许的方向"；
• 下标 0（上）和 2（左）是偶数 → 对应"偶数编号允许的方向"。
这样一来，判断"这次移动合不合规"就退化成了一次位运算：dirs 的下标 % 2是否等于k。相等即合规，不等即违规。违规时额外付penalty[i][j]，其中(i,j)是移动前所在的格子（注意不是目标格）。
三、状态数组与初始化
• 开一个三维数组
dis[i][j][k]，含义是：到达格子 (i,j)，且下一条行动的编号奇偶性为 k 时，已经付出的最小总费用。数组规模 2·m·n，初值全部设为无穷大（math.MaxInt），表示"尚未到达"。• 起点的处理是特殊的：人一开始就在 (0,0)，题目规定出发时先支付起点的进入费用
(0+1)×(0+1) = 1。此时一次行动都还没做，所以下一条行动是第 1 次（奇数），即k = 1。• 因此初始状态是
dis[0][0][1] = 1，并把这个三元组(费用=1, 行=0, 列=0, k=1)放进小根堆。堆里只有一个元素，天然满足堆性质，不需要再调初始化。
循环里反复做四件事：
1.弹出堆顶，即当前"费用最小、还没确定"的状态
(d, i, j, k)。堆按费用d排序，保证每次拿到的都是全局最小。2.终止判定：如果这个格子就是终点
(m-1, n-1)，直接返回d。这里可以立刻返回是因为 Dijkstra 的性质——所有边权非负（入口费和 penalty 都 ≥ 0），堆顶弹出的顺序就是代价递增的顺序，第一次弹出终点的那个代价，无论是奇数态还是偶数态，都已经是全局最小，后面再弹出终点只会更大。题目也不要求"到达时必须处于某个奇偶性"，落到终点即结束。3.惰性删除：如果
d > dis[i][j][k]，说明这是当初入堆后被更优路径超越的"过期记录"，直接跳过，不做扩展。4.扩展当前状态的两类（共 5 条）转移，做松弛：算出的新代价更小才更新
dis并入堆，否则丢弃。
因为网格一定连通、起点到终点必然可达，循环一定会命中第 2 步返回，不需要处理"堆空"的情况。
五、三类转移的具体代价公式
设当前状态是(i, j, k)，费用d，当前格子的罚值p = penalty[i][j]，目标格记为(x, y)。无论哪种转移，k都翻转为k^1。
转移
条件
新增代价
新状态
原地等待
p
（只付当前格的 penalty，不付入口费）
(i, j, k^1)合规移动
方向下标奇偶性 == k
只付目标格入口费(x+1)·(y+1)
(x, y, k^1)违规移动
方向下标奇偶性 != k
目标格入口费(x+1)·(y+1)+p（源格 penalty）
(x, y, k^1)
统一写法就是代码里的：d + (x+1)(y+1) + (idx%2 异或 k) × p。四个方向都要先做越界检查，越界的不产生转移。
注意一个容易忽略的点：入口费是"每次进入"都要付的，重新走进一个以前来过的格子同样要再付一次。状态里带上奇偶性维度之后，这种"绕回某格但奇偶性不同"的重复访问被正确区分了，不会算错。
六、用样例完整跑一遍（m=2, n=2, penalty = [[5,3],[1,4]]）
各格入口费：(0,0)=1，(0,1)=2，(1,0)=2，(1,1)=4。各格 penalty：(0,0)=5，(0,1)=3，(1,0)=1，(1,1)=4。
初始：堆 = { (1, 0,0, k=1) }，dis[0][0][1] = 1。
第 1 轮—— 弹出(1, (0,0), k=1)，未到终点，p = 5：
• 等待 → 代价 1+5 = 6，记
dis[0][0][0] = 6；• 向下到 (1,0)：下标 1（奇）== k=1，合规 → 1 + 2 = 3，记
dis[1][0][0] = 3；• 向右到 (0,1)：下标 3（奇）== k=1，合规 → 1 + 2 = 3，记
dis[0][1][0] = 3；• 上、左越界，忽略。
第 2 轮—— 弹出最小的(3, (1,0), k=0)，p = penalty[1][0] = 1：
• 等待 → 3+1 = 4，记
dis[1][0][1] = 4；• 向上到 (0,0)：下标 0（偶）== k=0，合规 → 3+1 = 4，但
dis[0][0][1]已是 1，不更新；• 向右到 (1,1)：下标 3（奇）≠ k=0，违规→ 3 + 4 + 1 = 8，记
dis[1][1][1] = 8；• 下、左越界。
第 3 轮—— 弹出(3, (0,1), k=0)，p = penalty[0][1] = 3：
• 等待 → 3+3 = 6，记
dis[0][1][1] = 6；• 向下到 (1,1)：下标 1（奇）≠ k=0，违规 → 3 + 4 + 3 = 10，比已有的 8 大，不更新；
• 向左到 (0,0)：合规 → 3+1 = 4，比 1 大，不更新。
第 4 轮—— 弹出(4, (1,0), k=1)，p = 1：
• 等待 → 4+1 = 5，比
dis[1][0][0] = 3大，不更新；• 向右到 (1,1)：下标 3（奇）== k=1，合规→ 4 + 4 = 8，记
dis[1][1][0] = 8。（这一条路径就是"先等待一拍把奇偶性掰成奇数，再合规地向右"，恰好与"直接违规向右"同价。）
第 5 轮起—— 依次弹出(6,(0,0),0)、(6,(0,1),1)等，它们扩展出的代价分别是 13、10 之类，都压不低已有记录，全部无效。
最终—— 堆中最小的剩余项是代价 8 的(1,1)状态（无论是 k=1 还是 k=0）。弹出时i=1=m-1、j=1=n-1，命中终点，返回8，与题目给出的解释完全一致（1 + 2 + 4 + 1）。
七、两个工程细节
•为什么返回值是 int64：所有边权非负，最优路径在状态图上不会绕环（绕环只会更贵），因此最多走 2·m·n − 1 步；每步最多付"入口费 ≤ m·n"加"penalty ≤ 10⁵"，量级可达 10¹⁰，超过 32 位整数范围，所以对外转成了
int64（内部dis用int，在 64 位平台上本身就是 64 位，安全）。•m、n 各自可达 10⁵，但 m·n ≤ 10⁵：所以按 m 行、每行 n 列来开二维数组是安全的，总元素数受
m·n约束，不会退化成 10¹⁰ 的分配。
设S = m·n（题目约束下 S ≤ 10⁵）。
状态数：V = 2·m·n = 2S（每个格子 × 两种奇偶性）。
边数：每个状态最多 1 条"等待"边 + 4 条"移动"边，所以E ≤ 5·V = 10·m·n。
时间复杂度：O(m·n · log(m·n))
每个状态被弹出并处理一次（过期记录直接跳过，代价可忽略），每次弹出与每次成功松弛各伴随一次堆操作 O(log V)；成功松弛的总次数不超过边数 E。总计 O((V + E)·log V) = O(m·n·log(m·n))。相对于只能 O(1) 转移的普通网格 DP，这里多出来的 log 因子来自"带权 + 可回头走"必须用堆。
额外空间复杂度：O(m·n)
• 距离数组
dis：2·m·n 个整数，即 O(m·n)；• 小根堆：条目数上界等于成功松弛次数，不超过 E = O(m·n)，每个条目是 4 个整数，仍是 O(m·n)；
• 除输入
penalty外没有其他随规模增长的结构。
代入上限 S = 10⁵：约 2×10⁵ 个状态、最多约 10⁶ 次入堆，距离数组约 1.6 MB，整体跑得非常轻松。
Go完整代码如下：
package main
import (
"container/heap"
"fmt"
"math"
)
// 奇数下标 1,3 对应向右或向下
// 偶数下标 0,2 对应向左或向上
var dirs = []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}
func minCost(m, n int, penalty [][]int)int64 {
dis := make([][][2]int, m)
for i := range dis {
dis[i] = make([][2]int, n)
for j := range dis[i] {
dis[i][j] = [2]int{math.MaxInt, math.MaxInt}
}
}
// 支付 1 的入口代价
dis[0][0][1] = 1
h := &hp{{1, 0, 0, 1}}
for {
top := heap.Pop(h).(tuple)
d, i, j, k := top.dis, top.x, top.y, top.k
if i == m-1 && j == n-1 {
returnint64(d)
}
if d > dis[i][j][k] {
continue
}
p := penalty[i][j]
// 原地不动
newDis := d + p
if newDis < dis[i][j][k^1] {
dis[i][j][k^1] = newDis
heap.Push(h, tuple{newDis, i, j, k ^ 1}) // k^1 切换行动编号的奇偶性
}
// 移动一步
for idx, dir := range dirs {
x, y := i+dir.x, j+dir.y
if0 <= x && x < m && 0 <= y && y < n {
// 如果 k 和 idx 的奇偶性不同，那么违反了奇偶性规则，需要额外支付 p 的代价
newDis = d + (x+1)*(y+1) + (idx%2^k)*p
if newDis < dis[x][y][k^1] {
dis[x][y][k^1] = newDis
heap.Push(h, tuple{newDis, x, y, k ^ 1}) // k^1 切换行动编号的奇偶性
}
}
}
}
}
type tuple struct{ dis, x, y, k int }
type hp []tuple
func (h hp) Len() int { returnlen(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() (v any) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }func main() {
m := 2
n := 2
penalty := [][]int{{5, 3}, {1, 4}}
result := minCost(m, n, penalty)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
import heapq
def min_cost(m: int, n: int, penalty: list[list[int]]) -> int:
# 索引 0：向左；索引 1：向右；索引 2：向上；索引 3：向下
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
inf = float("inf")
# dist[i][j][k] 表示到达 (i, j) 且下一次行动奇偶性为 k 时的最小费用
# k = 1 表示奇数编号行动，k = 0 表示偶数编号行动
dist = [[[inf, inf] for _ in range(n)] for _ in range(m)]
# 起点入口费用为 (0 + 1) * (0 + 1) = 1
# 行动编号从 1 开始，因此初始 k = 1
dist[0][0][1] = 1
heap = [(1, 0, 0, 1)] # (当前费用, 行, 列, 当前行动奇偶性)
while heap:
d, i, j, k = heapq.heappop(heap)
if i == m - 1 and j == n - 1:
return d
if d > dist[i][j][k]:
continue
p = penalty[i][j]
nk = k ^ 1 # 执行一次行动后，行动编号奇偶性切换
# 在当前单元格等待
new_dis = d + p
if new_dis < dist[i][j][nk]:
dist[i][j][nk] = new_dis
heapq.heappush(heap, (new_dis, i, j, nk))
# 尝试向四个相邻方向移动
for idx, (dx, dy) in enumerate(dirs):
x, y = i + dx, j + dy
if0 <= x < m and 0 <= y < n:
# 如果方向不符合当前行动编号的奇偶性要求，需要额外支付 penalty[i][j]
extra = ((idx & 1) ^ k) * p
new_dis = d + (x + 1) * (y + 1) + extra
if new_dis < dist[x][y][nk]:
dist[x][y][nk] = new_dis
heapq.heappush(heap, (new_dis, x, y, nk))
return-1if __name__ == "__main__":
m = 2
n = 2
penalty = [[5, 3], [1, 4]]
result = min_cost(m, n, penalty)
print(result)
C++完整代码如下：
using namespace std;
struct Tuple {
long long dis;
int x, y, k;
// 小根堆：按 dis 升序
bool operator>(const Tuple& o) const { return dis > o.dis; }
};long long minCost(int m, int n, vector int >>& penalty) {
// idx 0: 向左；idx 1: 向右；idx 2: 向上；idx 3: 向下
// 奇数下标 1,3 对应向右或向下
// 偶数下标 0,2 对应向左或向上
const pair< int , int > dirs[ 4 ] = {{ 0 , -1 }, { 0 , 1 }, { -1 , 0 }, { 1 , 0 }};
const long long INF = LLONG_MAX;
// dis[i][j][k]：到达 (i, j) 且下一次行动奇偶性为 k 的最小费用
vector 2 >>> dis(
m, vector 2 >>(n, {INF, INF}));
// 起点入口代价为 (0+1)*(0+1) = 1，行动编号从 1 开始，初始 k = 1
dis[ 0 ][ 0 ][ 1 ] = 1 ;
// 小根堆
priority_queue , greater > pq;
pq.push({ 1 , 0 , 0 , 1 });
while (!pq.empty()) {
Tuple t = pq.top();
pq.pop();
long long d = t.dis;
int i = t.x, j = t.y, k = t.k;
if (i == m - 1 && j == n - 1 ) {
return d;
}
if (d > dis[i][j][k]) {
continue ;
}
long long p = penalty[i][j];
int nk = k ^ 1 ; // 执行一次行动后，行动编号奇偶性切换
// 原地等待
long long newDis = d + p;
if (newDis < dis[i][j][nk]) {
dis[i][j][nk] = newDis;
pq.push({newDis, i, j, nk});
}
// 移动一步
for ( int idx = 0 ; idx < 4 ; ++idx) {
int x = i + dirs[idx].first;
int y = j + dirs[idx].second;
if (x >= 0 && x < m && y >= 0 && y < n) {
// 如果方向奇偶性与当前行动编号奇偶性不一致，违反规则，需额外支付 penalty
long long extra = (long long)((idx % 2 ) ^ k) * p;
newDis = d + (long long)(x + 1 ) * (y + 1 ) + extra;
if (newDis < dis[x][y][nk]) {
dis[x][y][nk] = newDis;
pq.push({newDis, x, y, nk});
}
}
}
}
return -1 ;
}
int main() {
int m = 2 , n = 2 ;
vector int >> penalty = {{ 5 , 3 }, { 1 , 4 }};
long long result = minCost(m, n, penalty);
cout << result << endl;
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴