題目：

問題描述： 在一個 m x n 的網格中，你位於網格的左上角 (0, 0)，需要移動到右下角 (m-1, n-1)。每次只能向右或向下移動，求有多少種不同的路徑可以到達終點。

解題思路

列出一些 mxn = 幾種路徑結果，來觀察有什麼規律，
1x1 = 1
1x2 = 1
1x3 = 1
1x4 = 1
在這些情況下，你只能一直向右移動。

2x1 = 1
3x1 = 1
4x1 = 1
只能一直向下移動。

嘗試推導更大的網格，發現是前面網格的結果推導出來的
2x2 = 1x2結果 + 2x1結果
2x3 = 1x3結果 + 2x2結果
2x4 = 1x4結果 + 2x3結果
m x n = m-1 x n結果 + m x n-1結果

dp[m][n] = dp[m-1][n] + dp[m][n-1];

對於某一個(m,n)來說，路徑數只能從上方來 dp[m-1][n] 或者左方來 dp[m][n-1] 的兩方向路徑數之和。

實作：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        // 初始化第 0 column 為 1
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        // 初始化第 0 row 為 1
        for (int j = 0; j < n; j++) {
            dp[0][j] = 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];
    }
};

時間複雜度：O(m * n)
空間複雜度：O(m * n)

筆記：

• 使用 vector<vector> dp(m, vector(n))，來建立一個 m x n 的二維動態規劃表。
• 用 vector<vector> dp(m, vector(n, 1)); 寫的話，可以建立一個全部元素都初始值為 1 的 m x n 的二維動態規劃表。

接下來嘗試優化空間複雜度

以3x3為例，結果如下，

[1, 1, 1]  // 第一行（初始值，只有一種路徑）
[1, 2, 3]  // 第二行（初始值）
[1, 3, 6]  // 第三行（初始值）

從新開始推算，

[1, 1, 1]  // 第一行（初始值，只有一種路徑）
[1, _, _]  // 第二行（初始值）
[1, _, _]  // 第三行（初始值）

壓縮成一維陣列(當前值已經包含第一行的值，也就是從上方來的路徑數)

[1, 1, 1]

更新一次第二行(所以只要當前值加上左方來的路徑數j-1就可以了)

[1, 2, 3]

更新一次第三行

[1, 3, 6]

公式變成
dp[j] = dp[j] + dp[j-1]
關鍵在於只需要保留當前行的路徑數量，因為每次計算新行時，只需要「從左方來的值」和「當前值」來計算結果，當前值已經包含從上方來的路徑數。

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

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

        return dp[n-1];
    }
};

時間複雜度：O(m * n)
空間複雜度：O(n), 如果m比n小，那麼可以改用一維m直式運算，也可以是O(min(m,n))。
不論是行數大於列數，還是列數大於行數，都能在空間複雜度上做到最佳化，
原本需要的二維陣列被壓縮成了一維陣列。

參考：
#62. Unique Paths