中 · 动态规划

最小路径和

不能向左也不能向上，所以到达一个格子时，你只可能来自上方或左方 —— 两种过去，选更便宜的那个。逐行填表，右下角就是答案。

一句话答案<code>best[i][j] = a[i][j] + min(best[i-1][j], best[i][j-1])</code>，第一行和第一列单独累加 —— 答案在 <code>best[n][m]</code>。

题目

输入: 第一行是 n 和 m（1 ≤ n, m ≤ 10）。接下来 n 行、每行 m 个整数（0 ≤ a ≤ 100），即网格。

输出: 从左上格走到右下格、只能向右或向下时，路径上格子之和的最小值。

样例:

输入输出
2 2
1 3
1 1		3
3 3
1 3 1
1 5 1
4 2 1		7

经典的 3×3 样例看起来该绕开 5 和 4 —— 手动追一下：1 → 1 → 5 反而比 1 → 3 → 1 更差。人眼不擅长这种比较，每个格子两次 min 擅长，表就是为此存在的。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 每个格子只有两种过去

因为不能向左向上，站上 (i, j) 的最小代价，就是「到 (i−1, j) 的最小」和「到 (i, j−1) 的最小」中较小的那个，再加上过路费 a[i][j]。递推式全部内容：best[i][j] = a[i][j] + min(best[i-1][j], best[i][j-1])。

提示 2 — 边界只有一种过去

第一行只能从左来，第一列只能从上来。所以它们用普通累加填充：best[1][j] = best[1][j-1] + a[1][j] —— 一个高频 bug 是把边界格子留成了网格值而不是累加和。

提示 3 — 贪心不够，表才够

诱人的捷径：每步挑更便宜的邻居走。会挂 —— 稍贵的一步可能换来后面的便宜通道。DP 表不会后悔，因为它在需要之前就把每个格子的真最优都算好了。当你想「就地拍板」时，换表格。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int best[12][12];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            if (i == 1 && j == 1) best[i][j] = a;
            else if (i == 1) best[i][j] = best[i][j - 1] + a;
            else if (j == 1) best[i][j] = best[i - 1][j] + a;
            else {
                int up = best[i - 1][j];
                int left = best[i][j - 1];
                best[i][j] = (up < left ? up : left) + a;
            }
        }
    }

    cout << best[n][m] << endl;
    return 0;
}

这就是一切路径问题背后的模式：换方向限制、换过路费、求最大 —— 表都不在乎。「以这里结尾的最优值」的一维表亲是 最大子段和,值得和这题对照着读。

深度解析

为什么这样做对

只能向右向下,所以每个格子恰好有两种前驱:上方和左方。「站上 (i, j) 的最小代价」= a[i][j] 加上两条来路中较便宜的那条。按行主序把每个格子都算出来,best[n][m] 就是答案,完全不需要搜索。

代价

时间空间都是 O(n·m):每个格子一次 min、一次加法。10×10 是 100 个格子;就算 1000×1000 也只是一百万个格子,瞬间完成。

常见错法

  • 边界格子只有一种过去:第一行必须从左累加,第一列必须从上累加。把它们直接写成网格值是最常见的错误答案。
  • 选了 min(up, left) 却忘了加上 a[i][j] 本身 —— 包括起点在内,每个格子的过路费都是强制的。
  • 贪心(每步挑更便宜的邻居)感觉对但会挂:稍贵的一步可能换来后面的便宜通道。表不会后悔,因为它在任何格子被需要之前就把全部格子算完了。

下一步

同一思想的「到此为止最优」一维版、而且不需要表的是 最大子段和。要数矩形而不是走路径,看 二维区间求和。

记住这两句

  • best[i][j] = a[i][j] + min(上方, 左方) —— 两种过去,选一个。
  • 边界做累加;它们没有第二个方向可以取 min。
🐞 这段是错的 —— 点开,亲手让它挂一次

边界格子直接用了网格值 —— 第一行从来没有累加过

#include <iostream>
using namespace std;

int best[12][12];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            if (i == 1 && j == 1) best[i][j] = a;
            else if (i == 1) best[i][j] = a;              // bug: no accumulation
            else if (j == 1) best[i][j] = a;              // bug: no accumulation
            else {
                int up = best[i - 1][j];
                int left = best[i][j - 1];
                best[i][j] = (up < left ? up : left) + a;
            }
        }
    }
    cout << best[n][m] << endl;
    return 0;
}