LeetCode Dynamic Programming_62. Unique Paths(Medium)

題目描述：

給定一個 m x n 的網格，從左上角出發，每次只能向右或向下移動一步，要到達右下角，有多少不同的路徑？

解題思路：

若直接沿用題目要的規則下去思考會比較困難

不過這邊有個淺藏的規律

start -> finish ⽅方法數 = finish -> start ⽅方法數 

那我們可反過來思考Finish走到start的方法數會較簡單

最下⾯面的 row及最右邊的 column，通往 finish 的⽅方法只有1種。可藉此反推走向 start 的⽅方法：通往某座標的⽅方法數 = 下⾯面座標的⽅方法數 + 右邊座標的⽅方法數

這是一個典型的動態規劃問題，我們可以使用動態規劃的方法來解決它。我們建立一個二維數組 dp，其中 dp[i][j] 表示從左上角到達網格中位置 (i, j) 的不同路徑數。

首先，我們可以初始化 dp[0][0] 為 1，因為左上角的位置就是起點，只有一種方法到達它。接下來，我們可以使用遞歸關係式來計算 dp[i][j]，即：

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

這是因為要到達位置 (i, j)，我們可以從上方的位置 (i-1, j) 或左方的位置 (i, j-1) 移動過來，所以 dp[i][j] 等於這兩個位置的不同路徑數之和。

我們需要進行雙重迴圈遍歷整個網格，從 (0, 0) 開始遍歷到 (m-1, n-1)。最後，dp[m-1][n-1] 就表示從左上角到達右下角的不同路徑數。

第一種作法.DP

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) {
                    dp[i][j] = 1;
                } else {
                    if (i > 0) dp[i][j] += dp[i - 1][j];
                    if (j > 0) dp[i][j] += dp[i][j - 1];
                }
            }
        }
        
        return dp[m - 1][n - 1];
    }
};




首先建立了一個二維數組 dp，然後使用雙重迴圈遍歷網格，根據遞歸關係式更新 dp[i][j] 的值。最後返回 dp[m-1][n-1] 即可。

這樣，我們使用動態規劃的方法，時間複雜度為 O(mn)，空間複雜度為 O(mn)，成功解決了這個不同路徑數的問題。

針對第一種作法 還能夠去把空間複雜度給優化

可以使用一維陣列來存儲中間結果，因為在計算每一行的結果時，只需要前一行的結果。這樣可以減少空間複雜度。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);  // 初始化為1，因為到達第一行的任何位置只有一種方法
        
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[j] += dp[j - 1];  // 更新dp[j]，表示到達位置(i, j)的不同路徑數
            }
        }
        
        return dp[n - 1];  // 返回右下角的結果
    }
};

上述程式中，我們使用一維陣列 dp 來存儲中間結果，初始化為1，然後進行雙重迴圈遍歷網格，按行更新 dp 陣列的值。最終返回 dp[n - 1]，即右下角的結果。

這種方法的時間複雜度仍然是 O(m*n)，但空間複雜度優化為 O(n)，僅使用一個一維陣列。這是一種更節省空間的DP解法。

第二種作法.數學排列組合 (時間複雜度 跟 空間複雜度 會更加理想)

從左上角到右下角的路徑實際上就是從 m+n-2 個步驟中選擇 m-1 個向下移動的步驟，或者選擇 n-1 個向右移動的步驟。我們可以使用排列組合的公式來計算這個結果。

排列組合的公式：C(m-1, m+n-2) = (m+n-2)! / [(m-1)! * (n-1)!]

在總數為m + n - 2中的數目中挑選n - 1個位置放豎著的走。

也就是我們說的C(m + n - 2)(n -1)的問題。

使用排列組合公式來計算不同路徑數。首先計算 (m+n-2)!，然後計算 (m-1)! 和 (n-1)!，最後將它們相除。這樣，我們優化了時間複雜度，不需要建立二維數組，而且優化了空間複雜度，只使用了一個變數。時間複雜度是 O(m + n)，空間複雜度是O(1)。

class Solution {
public:
    int uniquePaths(int m, int n) {
        int N = n + m - 2;
            int r = m - 1; 
            double res = 1;
            
            for (int i = 1; i <= r; i++)
                res = res * (N - r + i) / i;
            return (int)res;
    }
};

https://takeuforward.org/data-structure/grid-unique-paths-count-paths-from-left-top-to-the-right-bottom-of-a-matrix/