生活随笔
收集整理的這篇文章主要介紹了
Leetcode unique-paths
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
轉(zhuǎn)載自：http://blog.csdn.net/linhuanmars/article/details/22126357
原題鏈接:?http://oj.leetcode.com/problems/unique-paths/?
這道題是比較典型的動(dòng)態(tài)規(guī)劃的題目。模型簡(jiǎn)單，但是可以考核動(dòng)態(tài)規(guī)劃的思想。
我們先說(shuō)說(shuō)brute force的解法，比較容易想到用遞歸，到達(dá)某一格的路徑數(shù)量等于它的上面和左邊的路徑數(shù)之和，結(jié)束條件是走到行或者列的邊緣。因?yàn)槊織l路徑都會(huì)重新探索，時(shí)間復(fù)雜度是結(jié)果數(shù)量的量級(jí)，不是多項(xiàng)式的復(fù)雜度。代碼如下：?
[java]?view plaincopy
public?int?uniquePaths(int?m,?int?n)?{?? ????return?helper(1,1,m,n);?? }?? private?int?helper(int?row,?int?col,?int?m,?int?n)?? {?? ????if(row==m?&&?col==n)?? ????????return?1;?? ????if(row>m?||?col>n)?? ????????return?0;?? ????return?helper(row+1,col,m,n)+helper(row,col+1,m,n);?? }??
上面的代碼放到LeetCode中跑會(huì)超時(shí)，因?yàn)椴皇嵌囗?xiàng)式量級(jí)的。其實(shí)上一步中遞推式已經(jīng)出來(lái)了，就是res[i][j]=res[i-1][j]+res[i][j-1]，這樣我們就可以用一個(gè)數(shù)組來(lái)保存歷史信息，也就是在i行j列的路徑數(shù)，這樣每次就不需要重復(fù)計(jì)算，從而降低復(fù)雜度。用動(dòng)態(tài)規(guī)劃我們只需要對(duì)所有格子進(jìn)行掃描一次，到了最后一個(gè)得到的結(jié)果就是總的路徑數(shù)，所以時(shí)間復(fù)雜度是O(m*n)。而對(duì)于空間可以看出我們每次只需要用到上一行當(dāng)前列，以及前一列當(dāng)前行的信息，我們只需要用一個(gè)一維數(shù)組存上一行的信息即可，然后掃過(guò)來(lái)依次更替掉上一行對(duì)應(yīng)列的信息即可（因?yàn)樗枰玫降男畔⒍歼€沒(méi)被更替掉），所以空間復(fù)雜度是O(n)（其實(shí)如果要更加嚴(yán)謹(jǐn)，我們可以去行和列中小的那個(gè)，然后把小的放在內(nèi)層循環(huán)，這樣空間復(fù)雜度就是O(min(m,n))，下面的代碼為了避免看起來(lái)過(guò)于繁雜，就不做這一步了，有興趣的朋友可以實(shí)現(xiàn)一下，比較簡(jiǎn)單，不過(guò)代碼有點(diǎn)啰嗦）。實(shí)現(xiàn)的代碼如下：
[java]?view plaincopy
public?int?uniquePaths(int?m,?int?n)?{?? ????if(m<=0?||?n<=0)?? ????????return?0;?? ????int[]?res?=?new?int[n];?? ????res[0]?=?1;?? ????for(int?i=0;i<m;i++)?? ????{?? ????????for(int?j=1;j<n;j++)?? ????????{?? ???????????res[j]?+=?res[j-1];?? ????????}?? ????}?? ????return?res[n-1];?? }??
上面的方法用動(dòng)態(tài)規(guī)劃來(lái)求解，如果我們仔細(xì)的看這個(gè)問(wèn)題背后的數(shù)學(xué)模型，其實(shí)就是機(jī)器人總共走m+n-2步，其中m-1步往下走，n-1步往右走，本質(zhì)上就是一個(gè)組合問(wèn)題，也就是從m+n-2個(gè)不同元素中每次取出m-1個(gè)元素的組合數(shù)。根據(jù)
組合
的計(jì)算公式，我們可以寫(xiě)代碼來(lái)求解即可。代碼如下：
[java]?view plaincopy
public?int?uniquePaths(int?m,?int?n)?{?? ????double?dom?=?1;?? ????double?dedom?=?1;?? ????int?small?=?m<n??m-1:n-1;?? ????int?big?=?m<n??n-1:m-1;?? ????for(int?i=1;i<=small;i++)?? ????{?? ????????dedom?*=?i;?? ????????dom?*=?small+big+1-i;?? ????}?? ????return?(int)(dom/dedom);?? }??
上面的代碼求解了組合的結(jié)果，只需要做一次行或者列的掃描，所以時(shí)間復(fù)雜度是O(min(m,n))，而空間復(fù)雜度是O(1)。比起上面的兩種解法更優(yōu)。不過(guò)這里有個(gè)弊端，就是如果代碼中的dom和dedom如果不是double，而是用int，那么會(huì)很容易越界，因?yàn)檫@是一個(gè)階乘，所以大家在面試中討論這種方法要注意和提及越界的問(wèn)題。
上面介紹了幾種方法來(lái)求解這個(gè)問(wèn)題，其實(shí)都是比較簡(jiǎn)單的模型，只是提供了不同的思路。
Unique Paths II
是這道題的擴(kuò)展，給機(jī)器人增加了障礙，有興趣的朋友可以聯(lián)系一下。
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)
總結(jié)
以上是生活随笔為你收集整理的Leetcode unique-paths的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
