LeetCode 筆記：Unique Paths（不同路徑）

一、題目描述

機器人位於 m x n 網格的左上角（起點）。機器人每次只能向下或向右移動一步。機器人嘗試到達網格的右下角（終點）。問總共有多少條不同的路徑？

上圖為 3×7 的網格，共有多少條不同路徑？

註： m 和 n 最大為 100。

二、題目分析

這是一個經典的動態規劃問題。定義 dp[i][j] 為從起點走到 (i, j) 的路徑數。因為只能向下或向右走，所以狀態轉移方程為：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

邊界條件：第一行與第一列的所有格子路徑數皆為 1。

為了節省空間，可使用一維陣列模擬二維，將 (i, j) 映射為 k[i * n + j]，記憶體連續，效率更高。

三、示例代碼

#include <iostream>
using namespace std;

class Solution {
public:
    // 深度優先搜索，會超時
    int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) return 0;
        if (m == 1 || n == 1) return 1;
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }

    // 動態規劃
    int uniquePaths2(int m, int n) {
        int *k = new int[m * n];
        // 邊界初始化
        for (int i = 0; i < m; ++i) k[i * n] = 1;
        for (int j = 0; j < n; ++j) k[j] = 1;
        // 狀態轉移
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                k[i * n + j] = k[(i - 1) * n + j] + k[i * n + j - 1];
            }
        }
        int result = k[(m - 1) * n + n - 1];
        delete [] k;
        return result;
    }
};

四、數學解法小結

實際上，該問題可轉化為組合數學問題。從左上到右下共需 m + n - 2 步，其中向下 m - 1 步，向右 n - 1 步。路徑數即為從 m + n - 2 步中選擇 m - 1 步向下（或選擇 n - 1 步向右）的組合數：

或：

此解法時間複雜度 O(min(m,n))，空間 O(1)，為最優解。