算法是一種藝術，給人感覺很不好接近，但是一旦你和ta熟絡了，你就能發現這門藝術的內在是多麼美妙且多變。
對於前端來說，算法也許不是最重要的，在日常工作中，幾乎很少用到。所以很多人也不是很感冒。
不過呢，有句話這麼說的：面試造火箭，上班擰螺絲。咱們得先學習造火箭，才能有擰螺絲的機會。
莫得辦法，既然想要擰螺絲，就要有好活的老學到老的覺悟。否則連改錐都沒了。
那麼，看題。
給你一個表格，像這樣的:
從 (0, 0) 到 (M, N)移動，並假設，每次只能向下或者向右移動一步，那麼，請問一共有多少種不同的路徑。
乍一看，好像可以遍歷，依次向下或者向右找 (i + 1, j) 或者 (i, j + 1)， 直至 (N, M)
比如下面這個簡單版本：
有六種路徑：
整理一下，相當於：
從(0, 0)開始，因為我們只能向下或者向右，所以我們先選擇一條路去走，比如向右，這時候我們就走到了(1, 0)
打叉的部分不代表不能走，只是代表當前流程下，我們只能選其一，也就是右
然後我們在(1, 0)，繼續走，可以向右或者向下，我們依然選擇向右，這時候我們走到了(2, 0)
然後再往下走，直至走到(N, M)，
然後(1, 0)，選擇另外一條路，因為這僅僅是個 3*3 的表格，所以我們只能向下
然後繼續選擇一個方向走直至(M, N)。
如此往復。
這樣的話，其實可以轉換成一個遞歸，也就是從(i, j) => (i + 1, j) | (i, j + 1)，然後從(i + 1, j) => (x, y) 這樣的一個遞歸方程式，不過這樣性能是很差的，而且表格一旦規模變大，就會爆棧。
那麼，我們如何有效的解決這個問題呢？
動態規劃
ok，我們再次觀察這個表格，我們其實會發現一個規律，就是套娃。
沒錯，表格把表格套娃了。
這樣一來，參考俄羅斯套娃，每個娃娃其實都是一樣的，也就是本質一樣，只不過體量逐漸變大，並且最小的那個娃娃不能繼續套娃，也就是最小的那個娃娃就是起點。
如此一來，我們姑且可以用俄羅斯套娃來翻譯一下這套題。
問：N個俄羅斯套娃合體後的總重量是多少？
答：由於最小的一個套娃無法繼續套，並且可以得知這個套娃的重量，所以：
有二個套娃的時候，重量是最小的加上第二個
有三個套娃的時候，重量是兩個套娃的重量的加上第三個
有四個套娃的時候，重量是三個套娃的重量的加上第四個
.
.
.
.
有N個套娃的時候，重量是(N - 1)個套娃的重量加上第N個
由此，我們可以得到一個式子：
dp(i) = dp(i - 1) + dp(i)
有沒有感覺和表格題有些許類似？
我們可以任意 N * M 的右下角作為結束點，每一個都是一個套娃的角色，可能在當前環中是大套娃，但是到了下一環就成了小套娃，所以這個表格其實就是升級版的套娃。
聰明的你，是不是發現了這個升級點在哪？沒錯，就是一次從(1, 1)開始，每次都是套兩個娃，也就是理當前結束點最近的兩個娃 => (1, 0) 和 (0, 1)
這樣一來我們的公式自然而然就出來了，就是：
dp(N, M) = dp(N - 1, M) + dp(N, M - 1)
七點就是當N或者M為0的時候，也就是這個表格為一條直線，所以總路徑都是1
這樣我們的代碼也就很容易寫出來了，並且效率提升，不會有爆棧的問題，還做了之前的緩存。
<code>function taowa(table) { for (let yLen = table.length, y = yLen - 1; y >= 0; y--) { for ( let xLen = table[0].length, x = xLen - 1; x >= 0; x-- ) { if (x == xLen - 1 || y == yLen - 1) { table[y][x] = 1; } else { table[y][x] = table[y + 1][x] + table[y][x + 1]; } } } return table[y][x];}/<code>舉個例子： 4 * 5的表格有多少種路徑？
答： 35種
後續看到這，聰明的你會覺得，這個也太簡單了吧，沒錯，算法就是這樣。
難者不會，會者不難。
然後如果稍稍加點改造，可能又會花很長時間去這種類似 套娃 的規律，因為每種套娃的方式都不一樣。
比如，還是這樣表格，不求不同所有路徑數量，將每個cell換成一個數字，求左上角到右下角的經過路徑的路徑內數字相加的最小值。也就是求最優解。
如下圖：
這道題的代碼是什麼呢？初學動態規劃的朋友們可以一起討論討論
最後，簡單總結下。
問題總是變幻莫測，只要你能找到其中的規律，一定能找到對應的解法。
對於動態規劃這類問題，有幾個特點：
- 有重複子問題(套娃)
- 單項(左上 => 右下)
- 分析作圖後，結果類似二叉樹
閱讀更多 sandag 的文章
關鍵字: 算法 火箭 JavaScript
