題目

他說，有一個機器人會在m*n的棋盤格左上角start上，然後機器人每次只能向下或向右移一步到達右下角finish，他想要的是總共有幾種不同的路線可以到達。

Example 2:
Input: m = 3, n = 2
Output: 3

想法

這題讓我想到了高中數學也有一樣的題目，當時老師有教我們一個超快的方法，就是每個位置的路徑數量都是上方格子+左方格子的路徑數，用Example1的圖來呈現的話，大概就是這樣的:

所以我會先建一個dp[][]來儲存每一個格子的路徑數有多少，然後最上面跟最左邊的那兩排都給他一個初始值1，因為到他們那些地方的路徑數都只有1個，接著就從(1,1)開始像我那樣做上和左格的相加，最後回傳到finish的路徑有幾條，而這個就是我們存在dp[][]裡的。

程式碼

class Solution {
   public int uniquePaths(int m, int n) {
       int[][] dp = new int[m][n]; 

       for (int j = 0; j < n; j++) dp[0][j] = 1;
       for (int i = 0; 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];

   }
}

執行成功