題目網址：https://leetcode.cn/problems/unique-paths/

題意：有一機器人位於 m x n 網格的左上角, 機器人每次只能往下 or 往右一步, 機器人試圖抵達網格的右下角, 求總共幾條不同的路徑。

Solution 1：

想法：利用 DP, 定義 dp[i][j] 為從起點到 (i, j) 的方法數, 其中第一列和第一行方法數皆初始化為 1（因為只能往下、右移動）。要避免重複計算（圖中橘色圈起來的部分）, dp[i][j] = 其左邊格子的方法數 + 上方格子的方法數
➔ 得到 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 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];
    }
};
  • time：$O(m \cdot n)$ ➔ for loop
  • space：$O(m \cdot n)$ ➔ dp

Solution 2：

想法：改進 Solution 1, 因為 dp[i][j] 只會用到同一列的 dp[i][j - 1] 和上一列 dp[i - 1][j], 故不需要開到 $O(m \cdot n)$ space, 只需開到 $O(n)$

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);

        for (int i = 1; i < m; ++i) {
            vector<int> nextRow = dp;

            for (int j = 1; j < n; ++j) {
                nextRow[j] = nextRow[j - 1] + dp[j];
            }

            dp = move(nextRow);
        }

        return dp.back();
    }
};
  • time：$O(m \cdot n)$ ➔ for loop
  • space：$O(n)$ ➔ dp 和 nextRow

Solution 3：

想法：用到排列組合數學, 總共要走 m - 1 個 ⇩ 和 n - 1 個 ⇨, 可看成不盡相異物排列

$\binom{(m-1)+(n-1)}{m-1} = \binom{m+n-2}{m-1} = \dfrac{(m+n-2)(m+n-3) … n}{(m-1)(m-2) … 1}$

$= \dfrac{n}{1} \cdot \dfrac{n + 1}{2} … \dfrac{m+n-3}{m-2} \cdot \dfrac{m+n-2}{m-1}$

其中，$\binom{m+n-2}{m-1} = \binom{m+n-2}{n-1}$，故可以取 r = min(m, n) 來簡化計算

  • 若 r 取 m，則 分子 - 分母 = n - 1
  • 若 r 取 n，則 分子 - 分母 = m - 1

令 分母 = i = [0, r - 1]，k = m + n - 2，則 分子 = k - r + i

class Solution {
public:
    int uniquePaths(int m, int n) {
        const int k = m + n - 2;
        const int r = min(m, n) - 1;
        const int diff = k - r;
        double res = 1.0; // 要用 float 或 double

        for (int i = 1; i <= r; ++i) {
            res *= ((diff + i) / i);
        }

        return res;
    }
};
  • time：$O(min(m, n))$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間