這道題是比較典型的動態規劃的題目。模型簡單，但是可以考核動態規劃的思想。
我們先說說brute force的解法，比較容易想到用遞歸，到達某一格的路徑數量等於它的上面和左邊的路徑數之和，結束條件是走到行或者列的邊緣。因為每條路徑都會重新探索，時間復雜度是結果數量的量級，不是多項式的復雜度。代碼如下：
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中跑會超時，因為不是多項式量級的。其實上一步中遞推式已經出來了，就是res[i][j]=res[i-1][j]+res[i][j-1]，這樣我們就可以用一個數組來保存歷史信息，也就是在i行j列的路徑數，這樣每次就不需要重復計算，從而降低復雜度。用動態規劃我們只需要對所有格子進行掃描一次，到了最後一個得到的結果就是總的路徑數，所以時間復雜度是O(m*n)。而對於空間可以看出我們每次只需要用到上一行當前列，以及前一列當前行的信息，我們只需要用一個一維數組存上一行的信息即可，然後掃過來依次更替掉上一行對應列的信息即可（因為所需要用到的信息都還沒被更替掉），所以空間復雜度是O(n)（其實如果要更加嚴謹，我們可以去行和列中小的那個，然後把小的放在內層循環，這樣空間復雜度就是O(min(m,n))，下面的代碼為了避免看起來過於繁雜，就不做這一步了，有興趣的朋友可以實現一下，比較簡單，不過代碼有點啰嗦）。實現的代碼如下：
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+n-2步，其中m-1步往下走，n-1步往右走，本質上就是一個組合問題，也就是從m+n-2個不同元素中每次取出m-1個元素的組合數。根據組合的計算公式，我們可以寫代碼來求解即可。代碼如下：public int uniquePaths(int m, int n) {
double dom = 1;
double dedom = 1;
int small = m上面的代碼求解了組合的結果，只需要做一次行或者列的掃描，所以時間復雜度是O(min(m,n))，而空間復雜度是O(1)。比起上面的兩種解法更優。不過這裡有個弊端，就是如果代碼中的dom和dedom如果不是double，而是用int，那麼會很容易越界，因為這是一個階乘，所以大家在面試中討論這種方法要注意和提及越界的問題。
上面介紹了幾種方法來求解這個問題，其實都是比較簡單的模型，只是提供了不同的思路。Unique
Paths II是這道題的擴展，給機器人增加了障礙，有興趣的朋友可以聯系一下。
