面试刷题-动态规划-求解最短路径

题目链接

https://leetcode-cn.com/problems/minimum-path-sum/

题目描述

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

题目分析

这是一个典型的动态规划的题目。每个元素对应的最小路径与其相邻元素对应的最小路径有关。

具体实现上,创建二维数组 $\textit{dp}$,与原始网格的大小相同,$\textit{dp}[i][j]$表示从左上角出发到(i,j)位置的最小路径和。显然,$\textit{dp}[0][0]=\textit{grid}[0][0]$。对于$\textit{dp}$中的其余元素,通过以下状态转移方程计算元素值。

当i>0且j=0时,$\textit{dp}[i][0]=\textit{dp}[i-1][0]+\textit{grid}[i][0]$。

当i=0且j>0时,$\textit{dp}[0][j]=\textit{dp}[0][j-1]+\textit{grid}[0][j]$。

当i>0且j>0时,$\textit{dp}[i][j]=\min(\textit{dp}[i-1][j],\textit{dp}[i][j-1])+\textit{grid}[i][j]$。

最后得到$\textit{dp}[m-1][n-1]$的值即为从网格左上角到网格右下角的最小路径和。

实现代码

我实现的代码:

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0) {
return 0;
}
std::vector<std::vector<int> > sum(row, std::vector<int>(col, 0));
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (i == 0 && j == 0) {
sum[i][j] = grid[i][j];
} else if (i == 0 && j > 0) {
sum[i][j] = sum[i][j - 1] + grid[i][j];
} else if (i > 0 && j == 0) {
sum[i][j] = sum[i - 1][j] + grid[i][j];
} else {
sum[i][j] = std::min(sum[i][j - 1] + grid[i][j], sum[i - 1][j] + grid[i][j]);
}
}
}
return sum[row - 1][col - 1];
}
};

官方实现的代码:

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0) {
return 0;
}
int rows = grid.size(), columns = grid[0].size();
auto dp = vector < vector <int> > (rows, vector <int> (columns));
dp[0][0] = grid[0][0];
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[rows - 1][columns - 1];
}
};

复杂度分析

时间复杂度:O(mn),其中m和 n分别是网格的行数和列数。需要对整个网格遍历一次,计算dp的每个元素的值。

空间复杂度:O(mn),其中m和n分别是网格的行数和列数。创建一个二维数组 dp和网格大小相同。

空间复杂度可以优化,例如每次只存储上一行的dp值,则可以将空间复杂度优化到 O(n)。

优化空间复杂度到O(n)的代码实现:

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0) {
return 0;
}
int rows = grid.size();
int columns = grid[0].size();
auto dp = vector<int>(columns);
dp[0] = grid[0][0];
for (int i = 1; i < columns; i++) {
dp[i] = dp[i - 1] + grid[0][i];
}
for (int j = 1; j < rows; j++) {
dp[0] = dp[0] + grid[j][0];
for (int k = 1; k < columns; k++) {
dp[k] = std::min(dp[k] + grid[j][k], dp[k - 1] + grid[j][k]);
}
}
return dp[columns - 1];
}
};

除非注明,否则均为[半杯茶的小酒杯]原创文章,转载必须以链接形式标明本文链接

本文链接: http://www.banbeichadexiaojiubei.com/index.php/2020/12/26/%e9%9d%a2%e8%af%95%e5%88%b7%e9%a2%98-%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92-%e6%b1%82%e8%a7%a3%e6%9c%80%e7%9f%ad%e8%b7%af%e5%be%84/

半杯茶的小酒杯
我还没有学会写个人说明!
上一篇

02 RequestMappingHandlerMapping初始化过程

下一篇

【Android NDK】(一)cmake构建项目

你也可能喜欢

评论已经被关闭。

插入图片