輸入：兩個int m和n
輸出：一個int,表示不同路徑的個數(shù)。
規(guī)則：有一個m行n列的矩陣，一個機器人從左上角走到右下角，每次向下或者向右走一格。

分析：目的是要找到從(0,0)到(m-1,n-1)有多少種不同 的走法。如果m=3，n=2。我們按照下圖走一遍。知道有3種走法。先觀察每種走法向下的箭頭都是2個，向右的箭頭都是1個。所以可以得出結(jié)論無論哪種走法向右和向下的數(shù)量是一定的。向下的數(shù)量是m-1，向右的數(shù)量是n-1。從(0,0)到(m-1,n-1)要經(jīng)過m+n-2步。所以這就是一個組合題：$C_{m+n?2}^{m?1}$。

public int uniquePaths(int m, int n) {int a = Math.min(m,n)-1;int b = m+n-2;long p = 1;long q = 1;for(int i=0;i<a;i++){p = p * (b-i);q = q * (i+1);}return (int)(p/q);}

分析2：我們給這個矩陣每個方格用坐標(biāo)表示(i,j)。

我們用dp[i][j]表示走到坐標(biāo)(i,j)有多少種走法。
我們自己手畫一下知道dp[1][1]=2，就是有2種路徑到達(dá)(1,1)。看圖中能夠到達(dá)(1,1)只有可能是從(1,0)或者(0,1)這兩個坐標(biāo)走過來。那dp[1][1]與dp[1][0]、dp[0][1]是什么關(guān)系呢？
實際走一下，知道dp[0][1]=1，dp[1][0]=1，那么dp[1][1]=dp[1][0]+dp[0][1]。為了防止錯誤，再多走幾個格子:dp[2][0]=1,dp[2][1]=dp[2][0]+dp[1][1]。從含義角度講：經(jīng)過(0,1)點達(dá)到(1,1)和經(jīng)過(1,0)點到達(dá)(1,1)的路徑肯定是不相同的，所以用加法不會出錯，也不會計算重復(fù)了。所以得到動態(tài)方程：
$dp[i][j]=dp[i?1][j]+dp[i][j?1]$
第0行和第0列的數(shù)據(jù)需要單獨初始化。

public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];dp[0][0] = 1;for(int j=1;j<n;j++){dp[0][j]=1;}for(int i=1;i<m;i++){dp[i][0] = 1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j] = dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}

空間優(yōu)化：

public int uniquePaths(int m, int n) {int[] dp = new int[n];for(int j=0;j<n;j++){dp[j]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[j] = dp[j]+dp[j-1];}}return dp[n-1];}

參考鏈接

總結(jié)

以上是生活随笔為你收集整理的[dp] LeetCode 62. Unique Paths的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。