【多维动态规划】64. 最小路径和（面试真题+面试官调整后的题目）

64. 最小路径和

难度：中等
力扣地址：https://leetcode.cn/problems/minimum-path-sum/description/

1. 原题以及解法

1.1 题目

给定一个包含非负整数的 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] <= 200

1.2 分析过程

首先应当分析简单的情况：如下图所示，长度为 2 x 2 时的最小路径和过程

接着我们需要计算尺寸更大情况的最小路径。

分析结论

• 上图已经提到转移方程，即 dp[i][k] = min(dp[i-1][k], dp[i][k-1]) + grid[i][k] 。但是需要注意这个公式的适用场景：i >= 1, k >= 1。
• 对于 i == 0 以及 k == 0 的情况（第一行与第一列），通过累加的方式即可更新dp值。

1.3 解题代码

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int row = grid.size();int column = grid[0].size();vector<vector<int>> dp(row, vector<int>(column));dp[0][0] = grid[0][0];// 第一行每个点的最小路径for (int i = 1; i < column; i++) {dp[0][i] = grid[0][i] + dp[0][i - 1];}// 第一列每个点的最小路径for (int i = 1; i < row; i++) {dp[i][0] = grid[i][0] + dp[i - 1][0];}/** 对于 dp[i][k] 的计算规则为* dp[i][k] = min(dp[i - 1][k], dp[i][k - 1]) + grid[i][k]*/for (int i = 1; i < row; i++) {for (int k = 1; k < column; k++) {dp[i][k] = min(dp[i - 1][k], dp[i][k - 1]) + grid[i][k];}}return dp[row - 1][column - 1];}
};

2. 拓展（带条件的多维动态规划）

注：据可靠保熟消息，本题是一道面试题，面试官首先考察了与力扣第64题相同的，然后在这个基础上添加了这个条件，希望参与者手撕代码。

在这个题的基础上添加限制条件：存在一个或多个障碍物堵塞路径，如果题目中无路径则返回 -1。

如下是一个基于力扣第64题调整后的新题目：

2.1 拓展题

问题描述

给定一个 m x n 的网格，其中每个单元格包含一个非负整数，表示到达该单元格的费用。同时，网格中可能存在若干不可通行的障碍物，障碍物用 -1 表示。你的任务是找到从左上角 (0, 0) 到右下角 (m-1, n-1) 的路径，使得路径上的数字总和最小。如果不存在路径，请返回 -1。

输入

• 一个二维数组 grid，grid[i][j] 为网格中的数值，其中 grid[i][j] >= 0 表示可通行，grid[i][j] == -1 表示不可通行的障碍物。

输出

• 返回从左上角到右下角的路径上的数字总和的最小值。如果不存在这样的路径，返回 -1。

示例 1

输入

grid = [[1, 3, 1],[1, -1, 1],[4, 2, 1]
]

输出

7

解释

最优路径为 (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)，路径费用为 1 + 1 + 4 + 1 + 1 = 7。

当然可以，这里是一个包含不可通行案例的示例：

---

示例 2

输入

grid = [[1, 3, -1],[2, -1, 3],[-1, 2, 1]
]

输出

-1

解释

在这个网格中，位置 (2, 0), (1, 1), (0,2) 是一个障碍物，导致从左上角 (0, 0) 到右下角 (2, 2) 的路径不可达，因此返回 -1。

---

这样是否满足你的要求？

提示

• m 和 n 的范围是 [1, 100]。
• 网格中的数值在 [0, 100] 范围内。

2.2 拓展解题代码

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;/*** 基于力扣64题的变形题，详情请参考：https://smileyan.blog.csdn.net/article/details/142346755*/class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int row = grid.size();int column = grid[0].size();vector<vector<int>> dp(row, vector<int>(column));dp[0][0] = grid[0][0];// 第一行每个点的最小路径int barricade = -1;for (int i = 1; i < column; i++) {if (dp[0][i - 1] == barricade || grid[0][i] == barricade) {dp[0][i] = barricade;} else {dp[0][i] = grid[0][i] + dp[0][i - 1];}}// 第一列每个点的最小路径for (int i = 1; i < row; i++) {if (dp[i - 1][0] == barricade || grid[i][0] == barricade) {dp[i][0] = barricade;} else {dp[i][0] = grid[i][0] + dp[i - 1][0];}}/** 对于 dp[i][k] 的计算规则为* dp[i][k] = min(dp[i - 1][k], dp[i][k - 1]) + grid[i][k]*/for (int i = 1; i < row; i++) {for (int k = 1; k < column; k++) {if (grid[i][k] == barricade || (dp[i - 1][k] == barricade && dp[i][k - 1] == barricade)) {dp[i][k] = barricade;} else if (dp[i - 1][k] == barricade) {dp[i][k] = dp[i][k - 1] + grid[i][k];} else if (dp[i][k - 1] == barricade) {dp[i][k] = dp[i - 1][k] + grid[i][k];} else {dp[i][k] = min(dp[i - 1][k], dp[i][k - 1]) + grid[i][k];}}}return dp[row - 1][column - 1];}
};int main() {Solution solution;vector<vector<int>> grid1 = {{1, 3, 1},{1, 5, 1},{4, 2, 1}};int result1 = solution.minPathSum(grid1);cout<<result1<<" -> 7"<<endl;vector<vector<int>> grid2 = {{1, 2, 3},{4, 5, 6}};int result2 = solution.minPathSum(grid2);cout<<result2<<" -> 12"<<endl;vector<vector<int>> grid3 = {{1, -1, 3},{4, -1, 6}};int result3 = solution.minPathSum(grid3);cout<<result3<<" -> -1"<<endl;vector<vector<int>> grid4 = {{1, -1, 3},{4, 1, 6}};int result4 = solution.minPathSum(grid4);cout<<result4<<" -> 12"<<endl;vector<vector<int>> grid5 = {{1, 3, 1},{1, 5, 2},{-1, 2, 1}};int result5 = solution.minPathSum(grid5);cout<<result5<<" -> 8"<<endl;vector<vector<int>> grid6 = {{1, 3, -1},{1, -1, 2},{-1, 2, 1}};int result6 = solution.minPathSum(grid6);cout<<result6<<" -> -1"<<endl;vector<vector<int>> grid7 = {{-1, 3, 1},{1, 1, 2},{1, 2, 1}};int result7 = solution.minPathSum(grid7);cout<<result7<<" -> -1"<<endl;vector<vector<int>> grid8 = {{1, 3, 1},{1, 1, 2},{1, 2, -1}};int result8 = solution.minPathSum(grid8);cout<<result8<<" -> -1"<<endl;return 0;
}

3. 总结

这道题应当与力扣第70题（爬楼梯）一样，作为动态规划的典型问题（热题100中多维动态规划类）。基于这道题面试官现场做了一个简单的调整，并不要求应聘者直接写代码求解出来，而是希望应聘者给出解决方案，并解释方案的可行性。

接下来的时间，还将围绕着这道题进行更多的摸索，动态规划是一个非常有意思的题：常常会因为阅读了 “参考答案” 而感到震惊。“怎么会这么简单”、“原来如此”。

感谢您的阅读、评论与点赞支持 ~ 感谢 ~

Smileyan
2024.09.21 23:48