題目：

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：遞歸

終點(diǎn)的路徑數(shù)= 所有能達(dá)到終點(diǎn)的點(diǎn)的路徑數(shù)之和，即為：路徑[m][n] =?路徑[m-1][n] +?路徑[m][n-1]

依次遞歸，直到start點(diǎn)（0，0）

?

代碼：

public static int uniquePaths(int m, int n) {if(n == 1 && m==1){//初始的位置return 1;}else if(n == 1 && m>1){return uniquePaths(1,m-1);}else if(n >1 && m==1){return uniquePaths(n-1,1);}else{return uniquePaths(n-1,m)+uniquePaths(n,m-1);}}

?

結(jié)果在m=17 n=23的時(shí)候超時(shí)了。所以意識到題目的限制條件是需要速度！

?

思路2：動態(tài)規(guī)劃

某一個(gè)點(diǎn)的路徑數(shù)= 所有能達(dá)到該點(diǎn)的點(diǎn)的路徑數(shù)之和，即為：路徑[m][n] =?路徑[m-1][n] +?路徑[m][n-1]

與遞歸不同的是，遞歸是從大往小算，動態(tài)規(guī)劃是從小往大算

?

代碼如下：

public static int uniquePaths(int m, int n) {int[][] arrResult = new int[m][n];for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(i == 0 && j== 0){ arrResult[0][0] = 1;}else if(i == 1 && j== 0){arrResult[1][0] = 1;}else if(i == 0 && j== 1){arrResult[0][1] = 1;}//以上是填充基礎(chǔ)值else{int row = 0;int column = 0;if(i> 0 ){row = arrResult[i-1][j];}if(j> 0 ){column = arrResult[i][j-1];}arrResult[i][j] = row + column; }}}return arrResult[m-1][n-1];}

?

轉(zhuǎn)載于:https://www.cnblogs.com/savageclc26/p/4871140.html

總結(jié)

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

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