【面试经典150 | 动态规划】不同路径 II

文章目录

写在前面
Tag
题目1
- 方法一：动态规划
- 方法二：空间优化
题目2
- 方法一：动态规划+空间优化
写在最后

写在前面

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

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

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

Tag

【动态规划-空间优化】【网格】

题目1

62. 不同路径

方法一：动态规划

本题是解题思路与【面试经典150 | 动态规划】最小路径和类似。

定义状态

定义 f[i][j] 表示机器人从网格左上角 (0, 0) 到位置 (i, j) 可以行走的不同位置数量。

转移关系

根据 “机器人每次只能向下或者向右移动一步”，可知到达 (i, j) 位置可以从 (i-1, j) 或 (i, j-1) 行走到达，于是有转移关系：

$f [i] [j] = f [i - 1] [j] + f [i] [j - 1]$

base case

因为 “机器人每次只能向下或者向右移动一步”，所以机器人从 (0, 0) 位置到第 0 行、第 0 列的不同路径数均为 1。

最后返回

最后返回 f[m-1][n-1]，表示机器人从网格左上角 (0, 0) 到网格右下角 (m-1, n-1) 可以行走的不同路径数量。

实现代码

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> f(m, vector<int>(n));for (int i = 0; i < m; ++i) {f[i][0] = 1;}for (int j = 0; j < n; ++j) {f[0][j] = 1;}for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {f[i][j] = f[i - 1][j] + f[i][j - 1];}}return f[m - 1][n - 1];}
};

复杂度分析

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

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

方法二：空间优化

仿照【面试经典150 | 动态规划】最小路径和中空间优化的思想，可以对朴素的动态规划法进行类似的空间优化。具体实现见代码。

实现代码

class Solution {
public:int uniquePaths(int m, int n) {int more = max(m, n);int less = min(m, n);vector<int> f(less, 1);for (int i = 1; i < more; ++i) {for (int j = 1; j < less; ++j) {/*f[j] = f[j] + f[j-1] 第二个f[j] 表示从上一行向下到达位置(i,j)f[j-1] 表示从上一列向右到达位置(i,j)*/ f[j] += f[j-1];         }}return f[less-1];}
};

复杂度分析

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

空间复杂度： $O(min\{m,n\})$ 。

题目2

63. 不同路径 II

方法一：动态规划+空间优化

对比上一个题目，本题增加了障碍物，解法上与上题基本一致。但是有几处变动：

遇到障碍物时 $f [i] [j] = 0$ ；
本题只需要考虑没有遇到障碍物即 $o b s t a c l e G r i d [i] [j]! = 1$ 时的不同路径数的问题，此时的状态转移方程也和上题一致。

朴素的动态规划方法

直接给出朴素的动态规划解法。

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();vector<vector<int>> f(m, vector<int>(n));f[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;// 初始化第 0 行for(int j = 1; j < n; ++j) {if (obstacleGrid[0][j] != 1) {f[0][j] = f[0][j-1];}}// 初始化第 0 列for (int i = 1; i < m; ++i) {if (obstacleGrid[i][0] != 1) {f[i][0] = f[i-1][0];}}// 计算一般位置for (int i = 1; i < m; ++i) {for(int j = 1; j < n; ++j) {if (obstacleGrid[i][j] != 1) {f[i][j] = f[i-1][j] + f[i][j-1];}}}return f[m-1][n-1];}
};

空间优化

先贴出代码

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();int more = max(m, n), less = min(m, n);bool rowMore = (more == m);vector<int> f(less);f[0] = (obstacleGrid[0][0] == 0);for (int i = 0; i < more; ++i) {for (int j = 0; j < less; ++j) {if ((rowMore && obstacleGrid[i][j] == 1) || (!rowMore && obstacleGrid[j][i] == 1)) {f[j] = 0;continue;}if ((rowMore && j-1 >= 0 && obstacleGrid[i][j-1] == 0) || (!rowMore && j-1 >= 0 && obstacleGrid[j-1][i] == 0)) {f[j] += f[j-1];}}}return f[less-1];}
};

我们使用布尔变量 rowMore 来表示网格的行数是都大于列数：

如果行数大于等于列数，则有 rowMore =true，此时按行更新 f；如果 (i, j) 位置有障碍物则更新 f[j] = 0；如果前一列的位置没有障碍物，则可以从前一列到达本列，更新 f[j] = f[j] + f[j-1]，其中第二个 f[j] 表示上一行的位置 (i-1, j) 的不同路径数。
如果行数小于列数，则有 rowMore =false，此时按列更新 f；如果 (j, i) 位置有障碍物则更新 f[j] = 0；如果前一行的位置没有障碍物，则可以从前一行到达本行更新 f[j] = f[j] + f[j-1]，其中第二个 f[j] 表示上一列的位置 (j, i-1) 的不同路径数。
可能会有点绕，读者还需多多阅读体会。如果实现想不明白，可以直接按照行来更新 f，这样空间复杂度为 $O (n)$ 。