网格中的最小路径代价 图解题解

这道题到底在问什么

输入

grid=[[5,3],[4,0],[2,1]], moveCost=[[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]

输出

17(路径 5 到 0 到 1)

输入

grid=[[5,1,2],[4,0,3]], moveCost 见题面

输出

6(路径 2 到 3)

最优解：一步一步想明白

1. 3记牢这套转移:每一格的最小代价,等于自己的格值,加上「从上一行所有来路里挑一条最省的」。下面就照着这句,从第 0 行开始一格一格填。
2. 4这是舞台上的动态规划表,一开始每个格子先写上它在 grid 里的原始值:第 0 行是 5 和 3,第 1 行是 4 和 0,第 2 行是 2 和 1。接下来从第 1 行起,我们会把每格改写成「到达这格的最小总代价」,格值本身则并进代价里。第 0 行没有移动,它的代价就等于格值,可以直接定下来。
3. 5先填第 0 行,它是所有路径的起点。因为从第一行出发本身不产生移动代价,所以到第 0 行每一格的最小代价,就等于它自己的格值。列 0 这格值是 5,f 就记 5,标成绿色确定下来。
4. 6同理,第 0 行列 1 这格值是 3,到它的最小代价就是 3。第 0 行两格都定了,f 这一行是 [5, 3]。这一行是后面所有计算的地基,往下每一格都要回头看它。
5. 7往下走之前,先把 moveCost 怎么查说清楚。它有 m 乘 n 行,行号从 0 到 m 乘 n 减 1,查表用的是「出发那格里的数值 v」当行号,不是坐标。比如上一行列 0 的值是 5,要落到本行列 0,查的就是 moveCost 第 5 行第 0 列。这个「按值查行」是本题最容易记错的地方,盯住它。
6. 8现在算格子 (1,0),它的值是 4。先试第一条来路:从上一行 列 0 过来。那格的最小代价 f 是 5,它的格值是 5,要落到本行列 0,查 moveCost 第 5 行第 0 列得移动代价 14。三样加起来:5 加 14 加 4 等于 23。
7. 9再试另一条来路:从上一行 列 1 过来。那格 f 是 3,格值 3,移到本列的代价查表得 18。合计 3 加 18 加 4 等于 25。和上一条 23 摆一起比,谁小取谁。
8. 10两条来路的代价是 23 和 25,取更小的 23。所以到 (1,0) 的最小总代价就是 23,它是从上一行 列 0 接过来的。把这格填成 23,标绿确定。
9. 11现在算格子 (1,1),它的值是 0。先试第一条来路:从上一行 列 0 过来。那格的最小代价 f 是 5,它的格值是 5,要落到本行列 1,查 moveCost 第 5 行第 1 列得移动代价 3。三样加起来:5 加 3 加 0 等于 8。
10. 12再试另一条来路:从上一行 列 1 过来。那格 f 是 3,格值 3,移到本列的代价查表得 6。合计 3 加 6 加 0 等于 9。和上一条 8 摆一起比,谁小取谁。
11. 13两条来路的代价是 8 和 9,取更小的 8。所以到 (1,1) 的最小总代价就是 8,它是从上一行 列 0 接过来的。把这格填成 8,标绿确定。
12. 14第 1 行两格都算完了,f 变成 [23, 8]。注意此刻格子里显示的已经不是原始格值,而是「到这格的最小总代价」。第 2 行往上看的就是这两个数;原始格值 4 和 0 只在查移动代价时还用得上。
13. 15现在算格子 (2,0),它的值是 2。先试第一条来路:从上一行 列 0 过来。那格的最小代价 f 是 23,它的格值是 4,要落到本行列 0,查 moveCost 第 4 行第 0 列得移动代价 2。三样加起来:23 加 2 加 2 等于 27。
14. 16再试另一条来路:从上一行 列 1 过来。那格 f 是 8,格值 0,移到本列的代价查表得 9。合计 8 加 9 加 2 等于 19。和上一条 27 摆一起比,谁小取谁。
15. 17两条来路的代价是 27 和 19,取更小的 19。所以到 (2,0) 的最小总代价就是 19,它是从上一行 列 1 接过来的。把这格填成 19,标绿确定。
16. 18现在算格子 (2,1),它的值是 1。先试第一条来路:从上一行 列 0 过来。那格的最小代价 f 是 23,它的格值是 4,要落到本行列 1,查 moveCost 第 4 行第 1 列得移动代价 4。三样加起来:23 加 4 加 1 等于 28。
17. 19再试另一条来路:从上一行 列 1 过来。那格 f 是 8,格值 0,移到本列的代价查表得 8。合计 8 加 8 加 1 等于 17。和上一条 28 摆一起比,谁小取谁。
18. 20两条来路的代价是 28 和 17,取更小的 17。所以到 (2,1) 的最小总代价就是 17,它是从上一行 列 1 接过来的。把这格填成 17,标绿确定。
19. 21最后一行也填完了,f 是 [19, 17]。这两个数分别是「走到最后一行列 0」和「走到最后一行列 1」的最小总代价。因为终点可以是最后一行任意一列,答案就在这两个里挑小的,下一帧收束。
20. 22整张表填满了。最后一行的 f 是 [19, 17],因为终点可以是最后一行的任意一列,取里面最小的那个就是答案。17 比 19 小,所以最小总代价是 17,落在列 1。
21. 23答案定在最后一行列 1 那个 17。顺着填表时记下的「从哪来」往回倒:这格是从第 1 行列 1 接来的;第 1 行列 1 这格现在显示的是 DP 代价 8,它的原始格值是 0,这个 8 又是从第 0 行列 0 的 5 接来的。这样一路往上,就把最省的那条路摸出来了。
22. 24整条最优路径亮出来:第 0 行列 0 的 5,到第 1 行列 1 的 0,再到第 2 行列 1 的 1。三个格值 5 加 0 加 1 等于 6;第一步从值 5 移到列 1 代价 3,第二步从值 0 移到列 1 代价 8,两步合 11。6 加 11,正好是 17。和开头说的路径对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = grid[0]
        for i in range(1, m):
            g = [inf] * n
            for j in range(n):
                for k in range(n):
                    g[j] = min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j])
            f = g
        return min(f)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid[0].size();
        const int inf = 1 << 30;
        vector<int> f = grid[0];
        for (int i = 1; i < m; ++i) {
            vector<int> g(n, inf);
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    g[j] = min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j]);
                }
            }
            f = move(g);
        }
        return *min_element(f.begin(), f.end());
    }
};

import java.util.*;
class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length, n = grid[0].length;
        int[] f = grid[0];
        final int inf = 1 << 30;
        for (int i = 1; i < m; ++i) {
            int[] g = new int[n];
            Arrays.fill(g, inf);
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    g[j] = Math.min(g[j], f[k] + moveCost[grid[i - 1][k]][j] + grid[i][j]);
                }
            }
            f = g;
        }

        // return Arrays.stream(f).min().getAsInt();
        int ans = inf;
        for (int v : f) {
            ans = Math.min(ans, v);
        }
        return ans;
    }
}

复杂度

面试官可能追问