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

写在前面

本专栏专注于分析与讲解【面试经典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 ( m i n { m , n } ) O(min\{m,n\}) O(min{m,n})。

题目2

63. 不同路径 II

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

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

• 遇到障碍物时 $f[i][j]=0$；
• 本题只需要考虑没有遇到障碍物即 $obstacleGrid[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)$。

复杂度分析

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

空间复杂的：经过空间优化后的空间复杂度为 O ( m i n { m , n } ) O(min\{m,n\}) O(min{m,n})。朴素动态规划的时间复杂度为 $O(mn)$。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。