动态规划<7>最小路径和(minimum-path-sum)
本节为动态规划第七题：最小路径和(minimum-path-sum)，主要包括：问题描述，算法思路，复杂度分析，C++实现。
1. 问题描述
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
2. 解法
2.1 暴力法
最简单的思路，利用递归，对于每个元素，我们都考虑两条路径，即向右或者向下（到达该元素），在这两条路径中挑选路径权值较小的一个：cost[i,j]=grid[i][j]+min(cost(i+1,j),cost(i,j+1))。C++代码如下：
//1.暴力法，时间复杂度O(2^{m*n})，空间复杂度O(m+n)->递归的深度int calculate(vector<vector<int>>& grid, int i, int j) {if (i == grid.size() || j == grid[0].size()) return 100000;if (i == grid.size() - 1 && j == grid[0].size() - 1) return grid[i][j];return grid[i][j] + min(calculate(grid, i + 1, j), calculate(grid, i, j + 1));}int minPathSum(vector<vector<int>>& grid) {return calculate(grid, 0, 0);}
2.2 二维动态规划
新建一个与原矩阵大小相同的dp数组，dp[i][j]表示从坐标(i,j)到右下角的最小路径权值，初始化右下角的dp值为对应的原矩阵值，然后填这个dp数组，对于每个元素考虑移动到向右或向下移动到该元素，得到如下递推公式，和暴力法类似：
dp[i,j]=grid[i][j]+min(dp(i+1,j),dp(i,j+1))，C++代码如下：
//2.二维动态规划，时间复杂度O(m*n)，空间复杂度O(m*n)int minPathSum(vector<vector<int>>& grid) {vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));for (int i = grid.size() - 1; i >= 0; i--) {for (int j = grid[0].size() - 1; j >= 0; j--) {//最后一行if (i == grid.size() - 1 && j != grid[0].size() - 1)dp[i][j] = grid[i][j] + dp[i][j + 1];//最后一列else if (j == grid[0].size() - 1 && i != grid.size() - 1)dp[i][j] = grid[i][j] + dp[i + 1][j];//其余else if (j != grid[0].size() && i != grid.size() - 1)dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);//右下角elsedp[i][j] = grid[i][j];}}return dp[0][0];}
2.3 一维动态规划
实际上可以用一维数组代替二维数组，dp数组的大小和行大小相同，初始化dp数组最后一个元素为右下角的元素值，然后向左更新dp数组：dp[j]=grid[i][j]+min(dp[j],dp[j+1])，C++代码如下：
//2.一维动态规划，时间复杂度O(m*n)，空间复杂度O(n)int minPathSum(vector<vector<int>>& grid) {vector<int> dp(grid[0].size());for (int i = grid.size() - 1; i >= 0; i--) {for (int j = grid[0].size() - 1; j >= 0; j--) {//最后一行if (i == grid.size() - 1 && j != grid[0].size() - 1)dp[j] = grid[i][j] + dp[j + 1];//最后一列else if (j == grid[0].size() - 1 && i != grid.size() - 1)dp[j] = grid[i][j] + dp[j];//其余else if (j != grid[0].size() && i != grid.size() - 1)dp[j] = grid[i][j] + min(dp[j], dp[j + 1]);//右下角elsedp[j] = grid[i][j];}}return dp[0];}
2.4 不需要额外空间的动态规划
自然，我们可以以用原矩阵作为dp数组，这样空间复杂度降到O(1)，状态转移方程列为：grid(i,j)=grid(i,j)+min(grid(i+1,j),grid(i,j+1))，C++代码如下：
//2.不需要额外空间的动态规划，时间复杂度O(m*n)，空间复杂度O(1)int minPathSum(vector<vector<int>>& grid) {for (int i = grid.size() - 1; i >= 0; i--) {for (int j = grid[0].size() - 1; j >= 0; j--) {//最后一行if (i == grid.size() - 1 && j != grid[0].size() - 1)grid[i][j] = grid[i][j] + grid[i][j + 1];//最后一列else if (j == grid[0].size() - 1 && i != grid.size() - 1)grid[i][j] = grid[i][j] + grid[i + 1][j];//其余else if (j != grid[0].size() && i != grid.size() - 1)grid[i][j] = grid[i][j] + min(grid[i + 1][j], grid[i][j + 1]);//右下角elsegrid[i][j] = grid[i][j];}}return grid[0][0];}
深度学习与数学
关注公号，发现更多
长按识别上方二维码关注