有個 m × n Grid（網格），robot 從左上角出發，而且每次只能：→ 往右↓ 往下
走到右下角總共有幾種不同走法？
例如 3 × 3：
S . .
. . .
. . E
總共有 6 條路。

2.比較
#417 Pacific Atlantic #62 Unique Paths
問題 哪些格子可以到海洋？ 共有幾條路？
核心 Reachability（可達性） Count（計數）
方法 DFS/BFS DP
會不會真的搜尋方向 會 不用列出每條路
Grid 有高度限制 沒高度，只能右/下

都是 Grid，但問題完全不同

3.2D DP（二維動態規劃）？

dp[x]只需要一個位置，所以是 1D DP。

dp[row][col]每個答案需要：第幾 row+第幾 col so 2D DP
dp[row][col] = 走到這一格總共有幾種方法。

4.Math / DP / Combinatorics 個別是什麼？
類型 這題
Math（數學） 用數學直接計算路徑數
Dynamic Programming 前面格子的答案算好，後面直接重用
Combinatorics（組合數學） 把「幾次右＋幾次下」看成排列組合

先學 DP，另外兩個不用展開。不需要把每條路真的走一次。
DP 直接算：
1 1 1
1 2 3
1 3 6
中間是 2只能從：上面來 → 1 種;左邊來 → 1 種;1 + 1 = 2
右下角：上面 = 3;左邊 = 3;3 + 3 = 6
完全不用列：路 1.2.3.

5.跟 Jump Game有一點像前面算過的資訊繼續利用，但本質不同
#55 / #45→ Greedy→ 維護最遠範圍
#62→ DP→ 累積每一格的路徑數

6.目前格子的答案，是由鄰居已經算好的答案組合出來。

7.2D DP 可以進一步壓成 1D，所以不用真的建立整張表：

class Solution {
public:
    int uniquePaths(int m, int n) {//算左上到右下共有幾條路
        vector<int> dp(n, 1);//第一排每格都只有 1 種走法

        for (int row = 1; row < m; ++row) {//從第二排開始
            for (int col = 1; col < n; ++col) {//從第二欄開始
                dp[col] += dp[col - 1];//上面的方法+左邊的方法
            }
        }

        return dp[n - 1];// 最右下角的路徑總數
    }
};

這行是整題靈魂：dp[col] += dp[col - 1];
執行前：dp[col] = 上面那格的方法數
dp[col - 1] = 左邊那格的方法數

所以：目前格= 上面+ 左邊
Time Complexity（時間複雜度）：O(m × n)
Space Complexity（空間複雜度）：O(n)

問題看起來很多可能↓能不能找到重複子問題↓把前面結果保存↓不重新計算↓建立 recurrence．
能否把大量可能性壓縮成少量狀態。

① 定義：dp[row][col]
② 找來源：目前這格可以從哪來
③ 寫關係：目前 = 上面 + 左邊
④ 設起點：第一排 / 第一欄
⑤ 一格一格往後算

DP 不把所有路走完；是算過一格後，把答案留下來給後面的格子直接用。