最低通行费

题目描述

$N \times N$ 的费用网格（ $1 \leqslant N < 100$ ，格子费用 $\leqslant 100$ ），从左上角走到右下角，每经过一个格子花 1 单位时间并缴纳该格费用，总时间不得超过 $2N-1$ ，只能上下左右移动且不能离开网格。输入第一行 $N$ ，随后 $N$ 行每行 $N$ 个整数；输出最少总费用（含起点与终点）。样例输入 5 及费用矩阵 1 4 6 8 10 / 2 5 7 15 17 / 6 8 9 18 20 / 10 11 12 19 21 / 20 23 25 29 33，输出 109。

思路

从 $(1,1)$ 到 $(N,N)$ 最少要走 $2N-2$ 步、经过 $2N-1$ 个格子，恰好等于时限，所以路径只能向右或向下。设 $dp[j]$ 为走到当前行第 $j$ 列的最小累计费用，DP 转移为 $dp[j]=\min(\text{上方},\text{左方})+a[i][j]$ ，滚动更新一行，答案即 $dp[N]$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    grid = [[next(data) for _ in range(n)] for _ in range(n)]

    # 第一行：只能从左边来，前缀和即最小费用
    dp = [0] * n
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]

    # 其余行：滚动数组，dp[j] = min(上方, 左方) + 当前格费用
    for i in range(1, n):
        row = grid[i]
        dp[0] += row[0]                       # 第一列只能从上方来
        for j in range(1, n):
            dp[j] = min(dp[j], dp[j - 1]) + row[j]

    print(dp[-1])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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// main.cpp：时限 2N-1 恰好等于单调路径的格子数，退化为只能向右/向下的网格 DP，滚动数组 O(N^2)。
/**
 * 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-10-05 08:02
 * update_at: 2026-10-05 08:02
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 105;

int n;
int a[MAXN][MAXN]; // a[i][j]：经过格子 (i,j) 要缴的费用，值域 <= 100，用 int 控制内存
ll dp[MAXN];       // dp[j]：滚到当前行时，走到本行第 j 列的最少累计费用

// 从 (1,1) 走到 (n,n)，只能向右或向下，求经过格子（含起终点）的最小费用和。
void solve() {
    // 第一行只能从左边走过来，前缀和即最小费用
    dp[1] = a[1][1];
    for (int j = 2; j <= n; ++j)
        dp[j] = dp[j - 1] + a[1][j];

    // 其余行滚动更新：更新前 dp[j] 是上方值，dp[j-1] 已是本行左方值
    for (int i = 2; i <= n; ++i) {
        dp[1] += a[i][1]; // 第一列只能从上方来
        for (int j = 2; j <= n; ++j) {
            ll best = dp[j]; // 从上方 (i-1,j) 来
            if (dp[j - 1] < best)
                best = dp[j - 1]; // 从左方 (i,j-1) 来
            dp[j] = best + a[i][j];
        }
    }

    printf("%lld\n", dp[n]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]);
    solve();
    return 0;
}

目录

题目描述

思路

参考代码