【面试经典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)$ 。