面试刷题-动态规划-求解最短路径
题目链接
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];
}
};
除非注明，否则均为[半杯茶的小酒杯]原创文章，转载必须以链接形式标明本文链接