LeetCode刷题之路-62. 不同路径

2024-01-23 10:38:58

LeetCode刷题之路-62. 不同路径

题目介绍

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向下 -> 向下

向下 -> 向下 -> 向右

向下 -> 向右 -> 向下

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths

解题思路

我去，这题我会，一看就是深搜DFS啊，嗖嗖嗖写了下，一看样例过了，就提交了一发，很快啊，TLE超时了。代码如下：

class Solution {
    private int m, n;
    private int ans; // 记录遍历到达(m, n)的个数
    public void dfs(int x, int y) {
        if(x > m || y > n) { // 越界
            return;
        }
        if(x == m && y == n) { // 到达(m, n),答案+1
            ans++;
            return;
        }
        // 当前位置(x, y) 有两个子问题
        dfs(x + 1, y); // 向下移动
        dfs(x, y + 1); // 向右移动
    }
    public int uniquePaths(int m, int n) {
        this.m = m;
        this.n = n;
        dfs(1, 1); // 从(1, 1)点出发
        return ans;
    }
}

大家请看题目的提示部分，用DFS做的话，时间复杂度将达到O(2^m*n)。指数爆炸，那是必然超时滴！

既然上面能过部分小规模样例，说明思路是对了，可能是细节上处理不够。我们对上面进行优化，可以发现，有些状态下的答案我们计算了多次，如(2, 3) ->(2, 4)和(1, 4) ->(2, 4)这两个状态变化过程，我们就会对(2, 4)这个状态进行多次重复计算。那既然重复计算了，那么我们就在第一次计算过后，记录一下结果，下次再用到时直接使用就好了，这就是记忆化搜索（备忘录）。请看代码：

class Solution {
    private int m, n;
    private int ans;
    private int[][] memo; // 备忘录数组
    public int dfs(int x, int y) {
        if(x >= m || y >= n) {
            return 0; // 越界返回0
        }
        if(x == m - 1 && y == n - 1) {
            return memo[x][y] = 1; // 到达(m - 1, n - 1), 返回1，并记录结果
        }
        if(memo[x][y] != 0) // 如果已经计算过了，直接返回结果即可
            return memo[x][y];
        memo[x][y] = dfs(x + 1, y) + dfs(x, y + 1); // 记录下结果
        return memo[x][y];
    }
    public int uniquePaths(int m, int n) {
        this.m = m;
        this.n = n;
        this.memo = new int[m][n];
        dfs(0, 0);  // 从(0, 0)点出发
        return this.memo[0][0];
    }
}

请注意，这次我们从(0, 0)出发遍历到(m - 1, n - 1)，这和从(1, 1)出发到(m, n)是一样的。

上面我们是自顶向下根据递归方法计算出结果的，现在我们反过来，从子问题直接迭代出当前状态的答案，即动态规划。

class Solution {
    public int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        int[][] dp = new int[m][n]; 
        // 边界条件是当j = 0或者 i = 0时，答案为1
        for(int i = 0; i < m; i++)
            dp[i][0] = 1;
        for(int j = 0; j < n; j++)
            dp[0][j] = 1;
        for(int i = 1; i < m; i++) { // 状态1
            for(int j = 1; j < n; j++) { // 状态2
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 从左边一个点或者上边一个点到达该状态
            }
        }
        return dp[m - 1][n - 1]; // 返回最终状态的结果
    }
}

结语

这道题我们运用了三种方法，也是一种不断优化的过程，即DFS -> 记忆化搜索 -> 动态规划。其中，DFS是其他两种算法的基础，因为如果正确写出DFS的话，那么就意味着记忆化搜索和动态规划最关键的问题解决了：状态转移方程，剩下只不过就是用数组存储已经计算出的结果就好了。

这道题是动态规划的入门题，没有从子问题解得到原问题解的复杂条件，直接用子问题的解相加得到原问题的解就好了。因此，大家能够更加直观地体会出DP的奥妙。

最后，希望此文章能给大家带来收获，谢谢大家！

码农公寓

LeetCode刷题之路-62. 不同路径

题目介绍

解题思路

结语

相关文章