X

LEETCODE 62. Unique Paths 解题思路分析(2种经典思路)

题目大意:

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

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

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

示例 1:

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

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。 
1. 向右 -> 向下 -> 向下 
2. 向下 -> 向下 -> 向右 
3. 向下 -> 向右 -> 向下

示例 3:

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

示例 4:

输入:m = 3, n = 3
输出:6

提示:

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

解题思路分析:

对我来说这是一道送分题,因为我之前很多文章都介绍过动态规划和dfs深度优先搜索之间的关系。如果你看过我总结的 LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(下) 这篇文章,你应该记得看到这种格子或者矩阵应该下意识想到使用dfs,本题也很明确的指出需要求解路径数量,那么显然就是为了dfs算法量身定做的题目。

解法一:DFS深度优先搜索

在起点和终点已经固定的情况下,是dfs中比较简单的一类。我们只需按照规则进行移动即可。我们定义一个递归函数dfs()用于模拟路径搜索,递归方法的返回值为从当前格子出发到达终点的路径数。对于每个格子,只能向下或者向右移动,因此当前位置到达终点的可能性一定是dfs(相邻下方格子) + dfs(相邻右方格子)。这里需要注意一下边界问题,在最下一行以及最右一列时只能向一个方向移动。对于终点位置,它到终点的方式只有原地不动这一种选择,因此直接返回1即可,这也是递归方法的结束。

最后再来考虑记忆数组,很明显,我们只要记住每一次递归方法的结果即可,即当前格子到达终点的路径个数。使用记忆数组的目的在于避免重复计算。

上代码~

class Solution {
    int[][] memo; // 记忆数组
    public int uniquePaths(int m, int n) {
        memo = new int[m][n]; // 初始化记忆数组
        return dfs(0,0,m,n); // dfs走起
    }
    // x: 当前横坐标
    // y: 当前纵坐标
    int dfs(int x, int y, int m, int n){
        if(x == m || y == n) return 0; // 越界时返回0
        if(x==m-1 && y==n-1) return 1; // 终点位置直接返回1
        if(memo[x][y]>0) return memo[x][y]; // 从记忆数组中读取已存在的数据,直接返回。
        // dfs(相邻下方格子) + dfs(相邻右方格子)是当前结果
        int res = dfs(x+1, y, m, n) + dfs(x,y+1, m, n); 
        memo[x][y] = res; // 将当前结果保存至记忆数组
        return res;
    }
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths.Memory Usage: 35.8 MB, less than 74.48% of Java online submissions for Unique Paths.


解法二:DP动态规划

动态规划的想法和dfs是相反的,但是思路却大同小异。我们先定义一个dp数组(功能和dfs的记忆数组几乎一致),dp[x][y]代表从起点到当前点的路径个数。我们在这里做一个比较:

dfs方法中memo[x][y]代表当前位置到终点的路径个数,

dp方法中dp[x][y]代表起点位置到当前位置的路径个数。

可以看出,dp方法更像是正向推理,而dfs则是反向。

回到DP解法,接下来我们需要对dp数组进行初始化操作。通过观察可知,最上方的一行中,每个格子只能通过其左方格子到达,因此第一行中每个格子和起点间的路径只有一条,即dp[0][y] = 1。同理最左列格子和起点间也仅存在唯一路径过,即dp[x][0] = 1。最后再看其他格子,我们很明显可以得出一个规律,对于任意一个格子,路径上连接他的上一个位置只能是他相邻上方或右侧格子,因此,到达当前位置的可能性也就是dp[相邻左侧] + dp[相邻上侧]。最终dp[终点]既是返回结果。

实现代码:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n]; // dp数组,dp[x][y]代表起点到当前位置的路径个数
        for(int i=0;i<m;i++) dp[i][0]=1; // 初始化第一列都是1
        for(int i=0;i<n;i++) dp[0][i]=1; // 初始化第一行都是1
        for(int i=1;i<m;i++){ // 循环每一个点(第一行和第一列除外)
            for(int j=1;j<n;j++){
                // 起点到当前位置的可能性为dp[相邻左侧] + dp[相邻上侧]
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths.Memory Usage: 35.7 MB, less than 85.29% of Java online submissions for Unique Paths.

总结:

两种解法的时间复杂度几乎相同,正如上方提到的,只是思考的方式不同而已,对于正向思考或者是逆向思考哪个更容易理解,这必然因人而异,希望本文能够对你有所帮助。我们下篇文章再见!

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-62-unique-paths-解题思路分析(2种经典思路)/
Categories: leetcode
kwantong: