最低通行费

题意

$N \times N$ 网格，从 $(1,1)$ 进、 $(N,N)$ 出，必须在 $(2N-1)$ 个单位时间内穿越，求经过格子费用之和的最小值。

$(2N-1)$ 步意味着恰好向右 $N-1$ 步、向下 $N-1$ 步——不能绕路，所以问题等价于"只能向右或向下走的最小费用路径"。

思路

直接枚举所有路径是 $\binom{2N-2}{N-1}$ 级别， $N=100$ 时不可行。先看一个可以验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-04 12:50
 * update_at: 2026-08-04 12:50
 */

// brute.cpp：小数据暴力解，使用选择序列递归枚举所有路径。
// 每一层递归在选择"下一步向右还是向下走"，走到底（到达 (n,n)）时结算并更新最优。
// 只能处理小数据：路径数是组合数 C(2n-2, n-1)，指数级。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int INF = 0x3f3f3f3f;

int n;                 // 网格边长
int a[MAXN][MAXN];     // 费用
int ans;               // 最小费用

// 当前在 (x, y)，已花费 sum
void dfs(int x, int y, int sum) {
    if (x == n && y == n) {          // 到达右下角，结算
        ans = min(ans, sum);
        return;
    }
    if (x < n) dfs(x + 1, y, sum + a[x + 1][y]); // 向下走
    if (y < n) dfs(x, y + 1, sum + a[x][y + 1]); // 向右走
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }

    ans = INF;
    dfs(1, 1, a[1][1]);
    cout << ans << '\n';
    return 0;
}

这个暴力把路线看成选择序列：每一层递归在选择"下一步向右还是向下"，到达 $(N,N)$ 就结算并更新最小费用。它正确但枚举了全部路径。

关键观察：只能向右/向下走，每个格子 $(i,j)$ 只可能从上方 $(i-1,j)$ 或左方 $(i,j-1)$ 走来——走到它的最小费用路径，一定来自这两个格子中更小的那个。

定义 $dp[i][j]$ = 从 $(1,1)$ 走到 $(i,j)$ 的最小费用：

dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + a[i][j]

边界 $dp[1][1] = a[1][1]$ ，其余格子初始化为 INF（越界来源 $dp[0][j]$ 、 $dp[i][0]$ 不能被 min 选中——这是最小版和最大版的关键差别）。答案 $dp[N][N]$ 。

以样例左上 $3 \times 3$ 局部（[1 4 6; 2 5 7; 6 8 9]）走一遍转移表：

i \ j	1	2	3
1	1	1+4=5	5+6=11
2	1+2=3	min(3,5)+5=8	min(8,11)+7=15
3	3+6=9	min(9,8)+8=16	min(16,15)+9=24

看第 3 行第 3 列： $dp[3][3]$ 的两个候选是上方的 $dp[2][3]=15$ 和左方的 $dp[3][2]=16$ ，取较小者再加 $a[3][3]=9$ ，得到 24。注意第一行的 $dp[1][2]=5$ 来自唯一的左方前驱——如果越界来源不是 INF，min 会错误地选中 0。逐格推进到 $dp[5][5]=109$ ，与样例一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-04 12:50
 * update_at: 2026-08-04 12:50
 */

/* AcWing 1018 最低通行费 */
/* 2N-1 步穿越 N×N 网格 ⇔ 只能向右/向下走（无绕路余地），
 * 网格 DP 求最小费用：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j]。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int n;                 // 网格边长
int a[MAXN][MAXN];     // a[i][j]：格子 (i,j) 的费用
int dp[MAXN][MAXN];    // dp[i][j]：从 (1,1) 到 (i,j) 的最小费用

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }

    // 起点边界；其余格子先置 INF，保证越界来源（dp[0][j]、dp[i][0]）不会被选中
    memset(dp, 0x3f, sizeof(dp));
    dp[1][1] = a[1][1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1)
                continue;
            // 从上方或左方走来，取费用较小者（越界来源是 INF，自然被排除）
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
        }
    }

    cout << dp[n][n] << '\n';
    return 0;
}

复杂度

$O(N^2)$ 时间、 $O(N^2)$ 空间。

总结

和摘花生（1015）是同一个网格路径 DP 模型，只差两个字母：max → min。但这一换就引出新坑——最小版必须把越界来源初始化为 INF，否则全局数组的 0 会被当成合法来源。记住这个对比，两个题一起学效果最好。

目录

题意

思路

代码

复杂度

总结