1.2D DP 壓成 1D 因為算目前這格只需：上+左
例如原本 2D：
1 1 1
1 2 3
1 3 6
算最後一排時，其實只需要上一排：
原本 dp = [1,2,3]
走到 col=1：dp[1] = 上面2 + 左邊1 = 3 補充看第二點
→ [1,3,3]

走到 col=2：dp[2] = 上面3 + 左邊3 = 6
→ [1,3,6]

所以不用保存整張表，一排就夠。

2.目前：
原本 dp = [1,2,3]
index 0 1 2
走到：col = 1就是第 2 欄。
dp[1]就是 dp 裡 index 1 的位置，也就是原本的 2。
dp[1] = 上面 2 + 左邊 1
= 3

原本：
[1,2,3]
↑
dp[1] = 上面那格的答案 2

更新時左邊：dp[0] = 1
dp[1] = 2 + 1 = 3
更新後：[1,3,3]

記:dp[col] 更新前 = 上面；dp[col-1] 更新後 = 左邊。

3.最快 Combinatorics組合數學
從左上走到右下：一定要往下m-1次、往右n-1次，共m + n - 2 次
問這些步驟裡，選哪m-1次是「往下」
挑哪 m-1 個位置放「往下」；剩下自然就是「往右」。
所以答案：C(m+n-2, m-1)

class Solution {
public:
    int uniquePaths(int m, int n) {//算總路徑數
        int total = m + n - 2;//共一定要走幾步
        int choose = min(m - 1, n - 1);//選較少一邊，算更快
        long long answer = 1;//組合數答案

        for (int i = 1; i <= choose; ++i) {//一步一步算組合數
            answer = answer * (total - i + 1) / i;// C(total, i)
        }

        return answer;//回傳所有不同路徑數
    }
};

最小例子 3×3：往右2次，往下2次，共4步，從4步選2步當「往下」C(4,2) = 6
Time O(min(m,n))、Space O(1)
總步數 = 右 + 下；排列順序不同就是不同路徑 → Combination。

例如其中一種：↓ → ↓ →另一種：→ ↓ → ↓每種不同排列就是一條不同路徑。

m、n不 X/Y軸；m = rows（列／上下方向）n = columns（欄／左右方向）

C(4,2)=6 是組合數，跟機率會用到同一套數學，但這裡不是在算機率。
C(4,2)= 4! / (2! × 2!)= (4×3)/(2×1)= 6
4 個步驟位置裡，挑 2 個位置放「↓」，有 6 種選法。

7.不是問總步數，而是問「有幾條不同路徑」。
所有路徑總步數其實都一樣：總步數 = (m-1) + (n-1)
差別只在「↓ 和 → 的排列順序」，所以才要算：總共有幾種排列→ C(m+n-2, m-1)
例如 3×3 每條都走 4 步，但有 6 種不同排列，所以答案是 6。

類型 重點 最小例子
排列 Permutation 順序不同算不同 ABC、ACB 是不同
組合 Combination 只選哪些，不看選順序 從 A/B/C 選 A、B：AB和BA 算同一組

但#62路徑的順序其實有差。
例如 2 次 ↓、2 次 →：
↓↓→→
↓→↓→
→↓→↓這些都是不同路徑。
還用組合 C(4,2)因為我們不是在選「↓、→ 的排列」，而是在選：
4 個步驟位置裡，哪 2 個位置放 ↓。
例如：
位置：1 2 3 4

選 {1,2} → ↓ ↓ → →補充在第九點
選 {1,3} → ↓ → ↓ →
選 {2,4} → → ↓ → ↓

每一種「位置組合」就唯一對應一條路徑。

所以：

ABC vs ACB 當然是不同排列；
#62 用 Combination，是因為「選哪些位置放 ↓」就已經把所有不同排列算進去了，而且不會重複計算相同的 ↓ 和 →。

9.共 4 個位置：
位置：1 2 3 4
選 {1,2} 代表：第1步 ↓第2步 ↓第3步 →第4步 →
選 {1,3}：第1步 ↓第2步 →第3步 ↓第4步 →
選 {2,4}：第1步 →第2步 ↓第3步 →第4步 ↓
先選哪些步驟位置放「↓」，其他位置自然全部是「→」。