【动态规划/路径问题】进阶「最小路径和」问题 ...

前言

今天是我们讲解动态规划专题中的 路径问题的第三天。

今天讲解的题目主要是为了巩固 上一讲 我和你分享的 DP 分析技巧。

另外，我在文章结尾处列举了我所整理的关于 路径问题 的相关题目。

路径问题 我按照编排好的顺序进行讲解（一天一道）。

你也先可以尝试做做，也欢迎你向我留言补充，你觉得与路径相关的 DP 类型题目 ~

题目描述

这是 LeetCode 上的64. 最小路径和，难度为 Medium。

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

网络异常，图片无法展示

示例 1：

网络异常，图片无法展示

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
复制代码

示例 2：

网络异常，图片无法展示

输入：grid = [[1,2,3],[4,5,6]]
输出：12
复制代码

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

动态规划解法

这道题是在 62. 不同路径的基础上，增加了路径成本概念。

我们可以根据问题来调整我们的「状态定义」：

定义 f[i][j] 为从 (0,0) 开始到达位置 (i,j) 的最小总和。

那么 f[n-1][m-1] 就是我们最终的答案，f[0][0]=grid[0][0] 是一个显而易见的起始状态。

由于题目限定了我们只能往下或者往右移动，因此我们按照当前位置可由哪些位置转移过来进行分析：

当前位置只能通过往下移动而来，即有 f[i][j] = f[i-1][j] + grid[i][j]
当前位置只能通过往右移动而来，即有 f[i][j] = f[i][j-1] + grid[i][j]
当前位置既能通过往下也能往右移动，即有 f[i][j] = min(f[i][j-1],f[i-1][j]) + grid[i][j]

代码：

class Solution {
    public int minPathSum(int[][] grid) {        
        int m = grid.length, n = grid[0].length;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    f[i][j] = grid[i][j];
                } else {
                    int top  = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
                    int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
                    f[i][j] = Math.min(top, left);
                }
            }
        }
        return f[m - 1][n - 1];
    }
}
复制代码

时间复杂度：O(n∗m)O(n*m)O(n∗m)
空间复杂度：O(n∗m)O(n*m)O(n∗m)

进阶

如果要输出总和最低的路径呢？（如果有多个答案，返回其中之一即可）

从原问题我们知道，我们需要从 (0,0) 一步步转移到 (m-1,n-1)。

也就是我们需要扫描完整个方块（转移完所有的状态），才能得到答案。

那么显然，我们可以使用额外的数据结构来记录，我们是如何一步步转移到 f[m-1][n-1] 的。

当整个 dp 过程结束后，我们再用辅助记录的数据结构来回推我们的路径。

同时，由于我们原有的 dp 部分已经创建了一个二维数组来存储状态值，这次用于记录「上一步」的 g 数组我们改用一维数组来记录。

代码：

class Solution {
    int m, n;
    public int minPathSum(int[][] grid) {        
        m = grid.length;
        n = grid[0].length;
        int[][] f = new int[m][n];
        int[] g = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    f[i][j] = grid[i][j];
                } else {
                    int top  = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
                    int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
                    f[i][j] = Math.min(top, left);
                    g[getIdx(i, j)] = top < left ? getIdx(i - 1, j) : getIdx(i, j - 1);
                }
            }
        }
        // 从「结尾」开始，在 g[] 数组中找「上一步」
        int idx = getIdx(m - 1, n - 1);
        // 逆序将路径点添加到 path 数组中
        int[][] path = new int[m + n][2];
        path[m + n - 1] = new int[]{m - 1, n - 1};
        for (int i = 1; i < m + n; i++) {
            path[m + n - 1 - i] = parseIdx(g[idx]);
            idx = g[idx];
        }
        // 顺序输出位置
        for (int i = 1; i < m + n; i++) {
            int x = path[i][0], y = path[i][1];
            System.out.print("(" + x + "," + y + ") ");
        }
        System.out.println(" ");
        return f[m - 1][n - 1];
    }
    int[] parseIdx(int idx) {
        return new int[]{idx / n, idx % n};
    }
    int getIdx(int x, int y) {
        return x * n + y;
    }
}
复制代码

也许你会觉得「输出」方案的代码太麻烦了。

这是因为我们找路径的过程是「倒着」找，而输出方案的时候则是「顺着」输出。

如果希望简化找路径的过程，我们需要对原问题进行等价转换：

将「(0,0) 到 (m-1,n-1) 的最短路径」转换为「从 (m-1,n-1) 到 (0,0) 的最短路径」，同时移动方向从「向下 & 向右」转换为「向上 & 向左」。

这样我们就能实现「找路径」的顺序和「输出」顺序同向。

调整定义 f[i][j] 为从 (m-1,n-1) 开始到达位置 (i,j) 的最小总和。

class Solution {
    int m, n;
    public int minPathSum(int[][] grid) {        
        m = grid.length;
        n = grid[0].length;
        int[][] f = new int[m][n];
        int[] g = new int[m * n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    f[i][j] = grid[i][j];
                } else {
                    int bottom = i + 1 < m ? f[i + 1][j] + grid[i][j] : Integer.MAX_VALUE;
                    int right  = j + 1 < n ? f[i][j + 1] + grid[i][j] : Integer.MAX_VALUE; 
                    f[i][j] = Math.min(bottom, right);
                    g[getIdx(i, j)] = bottom < right ? getIdx(i + 1, j) : getIdx(i, j + 1);
                }
            }
        }
        int idx = getIdx(0,0);
        for (int i = 1; i <= m + n; i++) {
            if (i == m + n) continue;
            int x = parseIdx(idx)[0], y = parseIdx(idx)[1];
            System.out.print("(" + x + "," + y + ") ");
            idx = g[idx];
        }
        System.out.println(" ");
        return f[0][0];
    }
    int[] parseIdx(int idx) {
        return new int[]{idx / n, idx % n};
    }
    int getIdx(int x, int y) {
        return x * n + y;
    }
}
复制代码

如果方块中存在负权，如何求解？

如果考虑方块中增加负权的话，自然还需要增加一个限制：每个格子只能访问一次，否则会存在无数次访问负权格子的路径。

这时候问题就转换为「图论」问题，变成一个「最小生成树」问题了。

将每个格子往右和往下两个方向看做两条无向边，使用 Prim算法/Kruskal算法 求解。

这部分我们在之后的图论再讲。

总结

今天，除了 LeetCode 的原问题以外，我还给介绍了两个「进阶」问题。

在「进阶一」输出方案问题中，我给你介绍了如何使用「一维数组」存储「二维信息」，这是一个常见的手段。以及如何通过问题等价变换来降低编码难度。

通过「进阶二」我向你展示了，同一道题换了一个前提条件，求解方法将截然不同。

改了一个前提条件之后，原本的解法对应的证明将会失效，原本的算法也就不能正确求解了。

类似的问题我在路径问题第一讲的「思考」中也问过。

这就是我们做算法题一定要讲「证明」的原因，搞清楚本质了才是真正会做。

路径问题（目录）

62.不同路径（中等）：路径问题第一讲

63.不同路径 II（中等）：路径问题第二讲

64.最小路径和（中等）：（本篇）

120.三角形最小路径和（中等）

931.下降路径最小和（中等）

1289.下降路径最小和 II（困难）

1575.统计所有可行路径（困难）

576.出界的路径数（中等）

1301.最大得分的路径数目（困难）

欢迎补充 ~

最后

这是我们「刷穿 LeetCode」系列文章的第 No.64 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

【动态规划/路径问题】进阶「最小路径和」问题 ...｜刷题打卡

前言

题目描述

动态规划解法

进阶

总结

路径问题（目录）

最后

热门文章

最新文章

相关电子书