【面试经典150 | 动态规划】最小路径和

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：动态规划
- 方法二：空间优化
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【动态规划-空间优化】【数组】

题目来源

64. 最小路径和

解题思路

方法一：动态规划

定义状态

朴素的动态规划方法是定义状态 dp[i][j]，表示从网格左上角 (0, 0) 位置到 (i, j) 位置的最小路径和。

状态转移

根据题目中 “每次只能向下或者向右移动一步”，可知到达位置 (i, j) 只能从 (i-1, j) 向下移动一步或者从 (i, j-1) 向右一步，因此有转移关系：

$\ge 1, j \ge 1$

base case

dp[0][0] = grid[0][0]。

对于网格 grid 中的第一行和第一列位置，只能从对应位置的左侧和上方的位置移动一步得到，于是需要进行如下方式的初始化：

// 第一列
for (int i = 1; i < m; ++i)
    dp[i][0] = dp[i - 1][0] + grid[i][0];

// 第一行
for (int j = 1; j < n; ++j) {
    dp[0][j] = dp[0][j - 1] + grid[0][j];
}

最后返回

dp[m-1][n-1] 表示从网格左上角到网格右下角的最小路径和。

实现代码

class Solution {
public:
	int minPathSum(vector<vector<int>>& grid) {
		int m = grid.size(), n = grid[0].size();
		vector<vector<int>> dp = vector<vector<int>>(m, vector<int>(n));
		dp[0][0] = grid[0][0];

		// 对于在第一行或者第一列
		 第一列
		for (int i = 1; i < m; ++i)
			dp[i][0] = dp[i - 1][0] + grid[i][0];

		 第一行
		for (int j = 1; j < n; ++j) {
			dp[0][j] = dp[0][j - 1] + grid[0][j];
		}

		// 对于不在第一行和第一列的元素
		for (int i = 1; i < m; ++i) {
			for (int j = 1; j < n; ++j) {
				dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
			}
		}
		return dp[m - 1][n - 1];
	}
};

复杂度分析

时间复杂度： $O (mn)$ ， $m$ 为网格 grid 的行数， $n$ 为网格的列数。

空间复杂度： $O (mn)$ 。

方法二：空间优化

方法一中朴素解法的空间复杂度可以进行优化，只需要使用 $O(min\{m, n\})$ 的复杂度即可解决。

我们以 示例 1 为例说明，如何使用线性空间解决本题。

网格的行数和列数一样，选择按行来更新最小路径和（选择列也可以），维护一个数组 dp 长度为 3。

初始化 dp = {1, 4, 5}，dp[0] 表示从位置 (0, 0) 到位置 (0, 0) 的最小路径和；dp[1] 表示从位置 (0, 0) 到位置 (0, 1) 的最小路径和；dp[2] 表示从位置 (0, 0) 到位置 (0, 2) 的最小路径和。

在网格的第一行（从 0 开始数），dp[0] 表示从位置 (0, 0) 到位置 (1, 0) 的最小路径和，因为只能从 (0, 0) 位置到 (1, 0) 位置，所以更新 dp[0] = dp[0] + grid[1][0]；dp[1] 表示从位置 (0, 0) 到位置 (1, 1) 的最小路径和，因为可以从 (1, 0) 位置向右或者 (0, 1) 位置向下移动到位置 (1, 1)，所以有 dp[1] = min(dp[0], dp[1]) + grid[i][j]…

具体实现见如下代码。

实现代码

class Solution {
public:
	int minPathSum(vector<vector<int>>& grid) {
		int m = grid.size();
		int n = grid[0].size();

		int more = max(m, n);
		int less = min(m, n);
		bool rowMore = more == m;	// 判断是否是行数大于等于列数
		vector<int> arr(less);      // 以较短维度的长度作为临时空间，比如列数较小
		int i, j;
		for (i = 0; i < less; ++i) {// 更新第 0 行的所有列，即初始化
			if (i == 0) {
				arr[i] = grid[0][0];
			}
			else {
				arr[i] = arr[i - 1] + (rowMore ? grid[0][i] : grid[i][0]);
			}
		}

		for (i = 1; i < more; ++i) {// 按照行进行更新
			arr[0] = arr[0] + (rowMore ? grid[i][0] : grid[0][i]);  // 更新 i 行 0 列的答案
			for (j = 1; j < less; ++j) {                            // 更新 i 行其他列的答案
				arr[j] = min(arr[j - 1], arr[j]) + (rowMore ? grid[i][j] : grid[j][i]);
			}
		}
		return arr[less-1];
	}
};

复杂度分析

时间复杂度： $O (mn)$ ， $m$ 为网格 grid 的行数， $n$ 为网格的列数。