題目
#

題目簡述
#

給一個 m×n 的網格，機器人位於左上角 (0,0)，目標是到達右下角 (m-1,n-1)。
機器人只能向下或向右移動，求有多少種不同的路徑可以到達目標。

範例
#

Example 1:

Input: m = 3, n = 7
Output: 28
Explanation: 從左上角到右下角有 28 種路徑

3 × 7 網格：

┌───┬───┬───┬───┬───┬───┬───┐
│ S │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │ E │
└───┴───┴───┴───┴───┴───┴───┘

S = 起點 (0,0)
E = 終點 (2,6)
路徑數量：28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: 從左上角到右下角有 3 種路徑：
1. 下 → 下 → 右
2. 下 → 右 → 下  
3. 右 → 下 → 下

3 × 2 網格：

┌───┬───┐
│ S │   │
├───┼───┤
│   │   │
├───┼───┤
│   │ E │
└───┴───┘

S = 起點 (0,0)
E = 終點 (2,1)
路徑數量：3

解題思路
#

這題要求我們計算從左上角到右下角的不同路徑數量。我們可以使用動態規劃來解決這個問題，通過建立一個二維 DP 陣列，其中 dp[i][j] 表示從 (0,0) 到 (i,j) 的路徑數量。

解法
#

創建一個 m×n 的 DP 陣列
初始化第一行和第一列為 1（因為到達這些位置只有一種路徑）
對於其他位置，路徑數量等於從上方來的路徑數量加上從左方來的路徑數量
返回右下角位置的路徑數量

步驟
#

初始化 DP 陣列：
- 創建 int[][] dp = new int[m][n]
初始化邊界：
- 第一行：dp[0][i] = 1（只能從左邊來）
- 第一列：dp[i][0] = 1（只能從上邊來）
填充 DP 陣列：
- 對於每個位置 (i,j)：dp[i][j] = dp[i-1][j] + dp[i][j-1]
返回結果：
- 返回 dp[m-1][n-1]

例子說明
#

m = 3, n = 3

步驟	DP 陣列狀態	說明
初始化	`[[0,0,0],[0,0,0],[0,0,0]]`	創建 3×3 的 DP 陣列
初始化第一行	`[[1,1,1],[0,0,0],[0,0,0]]`	`dp[0][i] = 1`
初始化第一列	`[[1,1,1],[1,0,0],[1,0,0]]`	`dp[i][0] = 1`
填充 (1,1)	`[[1,1,1],[1,2,0],[1,0,0]]`	`dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2`
填充 (1,2)	`[[1,1,1],[1,2,3],[1,0,0]]`	`dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3`
填充 (2,1)	`[[1,1,1],[1,2,3],[1,3,0]]`	`dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3`
填充 (2,2)	`[[1,1,1],[1,2,3],[1,3,6]]`	`dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6`

最終結果： 6 種不同的路徑

路徑說明：

右→右→下→下
右→下→右→下
右→下→下→右
下→右→右→下
下→右→下→右
下→下→右→右

完整程式碼
#

java

class Solution {
    public int uniquePaths(int m, int n) {
        // 創建 DP 陣列
        int[][] dp = new int[m][n];

        // 初始化第一列為 1
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        // 初始化第一行為 1
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }

        // 填充 DP 陣列
        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];
    }
}