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

从第一行走到最后一行，最小总代价怎么算

给一张 m 行 n 列的网格 grid，格子是互不相同的整数。从第一行出发，每步落到下一行任意一列，直到最后一行。总代价 = 沿途格值之和加每次跨行的移动代价；moveCost[v][j] 是从值 v 的格子落到下一行第 j 列的代价。题面例子 grid=[[5,3],[4,0],[2,1]]，最优路径 5 到 0 到 1，答案 17。

把每条路都枚举一遍，为什么行不通

直觉是枚举每条从头到尾的路比总代价。可每一行都能落到 n 列任意一个，m 行连乘是 n 的 (m−1) 次方条路，n 和 m 到 50 就跑不完。但走到某一格后，往下怎么走只跟站在这格、已花多少有关，所以不必记整条来路，只需记住走到每一格的最小代价。

逐行滚动，f[j] 记走到本行第 j 列的最省花费

设 f[j] 为从第一行走到本行第 j 列的最小总代价。第 0 行是起点、出发不付移动代价，f 就是格值。往下逐行推：算本行第 j 列的 f，枚举上一行每列 k 当来路，候选 = f[k] 加移到本列 j 的代价加本格值 grid[i][j]，取最小。

移动代价用出发格的数值查 moveCost 的行、不是坐标：上一行第 k 列的值是 grid[i−1][k]，就查 moveCost[grid[i−1][k]][j]。推下一行只用得到紧挨的上一行，只留它逐行推进，这就是滚动数组省空间的办法。

一行填满再填下一行，末行取最小收口

逐行往下填，第 0 行是格值，本行 f 算好后成为下一行的地基，一路压到最后一行。终点没指定落在哪列，末行每列的 f 是走到那列的最小代价，扫一遍取最小即答案。

拿 [[5,3],[4,0],[2,1]] 把每格逐步填一遍

moveCost=[[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]。第 0 行抄格值 f=[5, 3]。

第 1 行取两来路较小者。(1,0)：5 加 moveCost[5][0]=14 加 4 得 23，或 3 加 18 加 4 得 25，取 23。(1,1)：5 加 moveCost[5][1]=3 加 0 得 8，或 3 加 6 加 0 得 9，取 8。f=[23, 8]。

第 2 行（上一行 f=[23, 8]、格值 4 和 0）。(2,0)：23 加 moveCost[4][0]=2 加 2 得 27，或 8 加 moveCost[0][0]=9 加 2 得 19，取 19。(2,1)：23 加 4 加 1 得 28，或 8 加 moveCost[0][1]=8 加 1 得 17，取 17。末行 f=[19, 17]，最小 17 即答案。

复杂度，再逐个点名填表最常写反的四处

时间 O(m·n²)：m 行、每行 n 列、每列再枚举 n 条来路，三层嵌套。空间 O(n)，滚动数组只留上一行和本行两份，不存整张 m 乘 n 的表。

写反的四处：moveCost 按数值查行，当坐标查会查错行；本格值 grid[i][j] 要计入总代价，漏了偏小；来路是上一行任意一列而非正上方，少枚举会错过更省解；答案取末行 f 最小值，取第 0 列会漏掉更优解。

Python

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)

C++

#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());
    }
};

Java

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;
    }
}