leetcode62. Unique Paths

zqhxuyuan 发布于2019-08-16 10:38 / 3220人阅读

摘要：问一共有多少条独特的路线思路一通过递归实现计算。思路二杨辉三角在思路的指引下，我们可以尝试将递归的方法改变为循环的方法来解决。我们只需要确定在总部数中哪些步数右行或是哪些步数下行即可知道其对应的路径。这里运用到排列组合的思想。

题目要求

A robot is located at the top-left corner of a m x n grid (marked "Start" in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked "Finish" in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

一个机器人站在下标为（1，1）的起点走向下标为（m，n）的终点。机器人只允许往下走和往右走。问一共有多少条独特的路线？

思路一：Dynamic Programming

通过递归实现计算。根据题目可知，在任何一个方块，一共有两条路径，一条是往下走，一条是往右走，如果任何一条路径能够到达终点，则返回1，否则返回0。

    public int uniquePaths(int m, int n) {
        return uniquePaths(1,1,m, n);
    }
    
    public int uniquePaths(int currentRow, int currentColumn, int m, int n){
        if(currentRow==m || currentColumn==n){
            return 1;
        }    
        return uniquePaths(currentRow+1, currentColumn, m ,n ) + uniquePaths(currentRow, currentColumn+1, m, n);
    }

同样的思路，也可以从终点开始往回计算，如果能够到达起点，则返回1，否则返回0。

    public int uniquePaths2(int m, int n){
        if(m==1 || n==1){
            return 1;
        }
        return uniquePaths2(n-1, m) + uniquePaths2(n, m-1);
    }

但是，以上这两种方法都超时了。显然，当我们不需要知道具体路径选项的时候，遍历所有的路径就显得有些累赘且降低性能。

思路二：杨辉三角

在Dynamic Programming思路的指引下，我们可以尝试将递归的方法改变为循环的方法来解决。这里就运用到了数学中的杨辉三角。很显然，最左侧一行和最顶侧一行的到达路径数都是1，而任何一个非该行列的节点都可以通过左侧节点和上侧节点的路径数相加得到从起点出发到达自己共有的路径数。我们可以利用二维数组来实现叠加。代码如下：

    public int uniquePath3(int m, int n){
        int[][] map = new int[m][n];
        for(int i = 0; i
##思路三： 排列组合 ##
这里运用的是纯数学的思想。根据题目可知，从起点到终点的总步数是一定的，右行或下行的次数也是一定的。我们只需要确定在总部数中哪些步数右行或是哪些步数下行即可知道其对应的路径。这里运用到排列组合的思想。
    public int uniquePaths4(int m, int n){
        int totalPath = m + n - 2;
        int down = m-1;
        int right = n-1;
        if(down == 0 || right==0){
            return 1;
        }
        int count = Math.min(down, right);
        long result = 1;
        for(int i = 1 ; i<=count ; i++){
            result *= totalPath--;
            result /= i;
        }
        return (int) result;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 Paths unique Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70157.html

leetcode63. Unique Paths II

摘要：题目要求这是题目系列。存在路障的节点会在数组中被标记为。请问从起点到终点有多少条独立路径。思路和代码在的思路基础上，我们可以知道，如果某个节点上存在路障，那么任何从该节点前往终点的路径都将不存在。也就是说，该节点的路径数为。题目要求 Follow up for Unique Paths: Now consider if some obstacles are added to the...

eternalshallow 2019-08-15 10:37 评论0 收藏0
[LintCode/LeetCode] Unique Paths II

摘要：和完全一样的做法，只要在初始化首行和首列遇到时置零且即可。对了，数组其它元素遇到也要置零喏，不过就不要啦。 Problem Follow up for Unique Paths: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle...

firim 2019-08-14 15:29 评论0 收藏0
[Leetcode] Unique Paths 唯一路径

摘要：动态规划复杂度时间空间思路因为要走最短路径，每一步只能向右方或者下方走。所以经过每一个格子路径数只可能源自左方或上方，这就得到了动态规划的递推式，我们用一个二维数组储存每个格子的路径数，则。 Unique Paths I A robot is located at the top-left corner of a m x n grid (marked Start in the dia...

yangrd 2019-08-14 12:23 评论0 收藏0
[LintCode/LeetCode] Unique Paths

摘要：简单的动规题目，建立数组。坐标为矩阵的坐标，值为从左上角到这一格的走法总数。赋初值，最上一行和最左列的所有格子的走法都只有一种，其余格子的走法等于其左边格子走法与上方格子走法之和。最后，返回即可。 Problem A robot is located at the top-left corner of a m x n grid (marked Start in the diagram ...

Gu_Yan 2019-08-14 15:27 评论0 收藏0
[LeetCode] 609. Find Duplicate File in System

Problem Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms o...

sf190404 2019-08-19 11:11 评论0 收藏0