leetcode62. Unique Paths

zqhxuyuan 發(fā)布于2019-08-16 10:38 / 3226人閱讀

摘要：問一共有多少條獨特的路線思路一通過遞歸實現(xiàn)計算。思路二楊輝三角在思路的指引下，我們可以嘗試將遞歸的方法改變?yōu)檠h(huán)的方法來解決。我們只需要確定在總部數(shù)中哪些步數(shù)右行或是哪些步數(shù)下行即可知道其對應(yīng)的路徑。這里運用到排列組合的思想。

題目要求

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.

一個機(jī)器人站在下標(biāo)為（1，1）的起點走向下標(biāo)為（m，n）的終點。機(jī)器人只允許往下走和往右走。問一共有多少條獨特的路線？

思路一：Dynamic Programming

通過遞歸實現(xiàn)計算。根據(jù)題目可知，在任何一個方塊，一共有兩條路徑，一條是往下走，一條是往右走，如果任何一條路徑能夠到達(dá)終點，則返回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);
    }

同樣的思路，也可以從終點開始往回計算，如果能夠到達(dá)起點，則返回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);
    }

但是，以上這兩種方法都超時了。顯然，當(dāng)我們不需要知道具體路徑選項的時候，遍歷所有的路徑就顯得有些累贅且降低性能。

思路二：楊輝三角

在Dynamic Programming思路的指引下，我們可以嘗試將遞歸的方法改變?yōu)檠h(huán)的方法來解決。這里就運用到了數(shù)學(xué)中的楊輝三角。很顯然，最左側(cè)一行和最頂側(cè)一行的到達(dá)路徑數(shù)都是1，而任何一個非該行列的節(jié)點都可以通過左側(cè)節(jié)點和上側(cè)節(jié)點的路徑數(shù)相加得到從起點出發(fā)到達(dá)自己共有的路徑數(shù)。我們可以利用二維數(shù)組來實現(xiàn)疊加。代碼如下：

    public int uniquePath3(int m, int n){
        int[][] map = new int[m][n];
        for(int i = 0; i
##思路三： 排列組合 ##
這里運用的是純數(shù)學(xué)的思想。根據(jù)題目可知，從起點到終點的總步數(shù)是一定的，右行或下行的次數(shù)也是一定的。我們只需要確定在總部數(shù)中哪些步數(shù)右行或是哪些步數(shù)下行即可知道其對應(yīng)的路徑。這里運用到排列組合的思想。
    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;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~