leetcode62. Unique Paths

zqhxuyuan 發布于2019-08-16 10:38 / 3221人閱讀

摘要：問一共有多少條獨特的路線思路一通過遞歸實現計算。思路二楊輝三角在思路的指引下，我們可以嘗試將遞歸的方法改變為循環的方法來解決。我們只需要確定在總部數中哪些步數右行或是哪些步數下行即可知道其對應的路徑。這里運用到排列組合的思想。

題目要求

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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