從最佳的那個，到全部的數目
你在本階建過的每一個動態規劃——區間型的矩陣鏈、樹上動態規劃、Held-Karp 巡迴——回答的都是最佳化問題：找出「最好的」安排。狀態、轉移式、最佳子結構都還在，但計數型動態規劃把問題換成了「總共有幾種」安排。令人驚訝的是改動有多小。最佳化的轉移式寫的是 `best[s] = 對所有選擇取 (成本 + best[next]) 的最小值`，計數型的轉移式則寫成 `ways[s] = 對所有選擇把 ways[next] 加總`。最小值或最大值變成了加號，而成本項消失了，因為我們是在數數量、不是在算價錢。
為什麼這個加號是對的？它就是計數裡的「加法原理」：如果狀態 s 的各個選擇導向的是彼此不相交的完成方式——拿第一個物品和跳過它，永遠不可能產生出同一個整體安排——那麼總數就是各組大小的和。整座建築的成敗都繫於「不相交」這個詞。如果兩個不同的第一步選擇有可能完成成「同一個」物件，你就會重複計數，而那個和就成了謊言。所以計數型動態規劃背負著一個最佳化動態規劃沒有的隱藏義務：你必須把狀態定義成讓每個完整物件恰好由一條選擇路徑產生。弄錯了，程式照樣會跑、會回傳一個數字、然後默默地多算。
住在一個模數裡
計數會爆炸。一個規模為 n 的問題裡，路徑、鋪磚或序列的數目動輒是 n 的指數，遠遠超過一個 64 位元整數能裝下的範圍，所以計數問題幾乎總是要求把答案對某個質數（例如 1000000007）取模。這不是為了好玩硬加上去的麻煩——它正是讓答案能塞進一個機器字的原因。好消息是加法和乘法都和取模可交換：你可以在轉移式裡每個 `+` 和每個 `*` 之後就先約簡，最終的餘數不變。所以 `ways[s] = (ways[a] + ways[b]) % MOD` 既讓每個表格項都維持很小，又保留了真實計數的餘數。
但要誠實面對模算術丟掉了什麼。餘數告訴你的是計數對 p 取模的結果，而不是計數本身：你再也不能完全有把握地說「答案是不是至少一百萬？」、甚至「它是不是零？」，因為一個剛好是 p 倍數的真實計數會約簡成 0。你也失去了一般的比較——對 p 取模之下沒有「比較大」這回事——所以一個模算術的計數型動態規劃永遠不能兼差當最佳化動態規劃。還有一個減法陷阱潛伏在「用補集計數」的技巧裡：在許多語言中 `(a - b) % MOD` 可能變成負數，所以安全的慣用寫法是 `((a - b) % MOD + MOD) % MOD`。
逐位計數：一個就是前綴的狀態
計數型動態規劃有一個漂亮的特例叫數位動態規劃：數出區間 [L, R] 裡有多少整數滿足它十進位數字的某種性質——例如沒有相鄰的兩個數字相等、或數字和能被 7 整除。天真的做法是把每個數都列舉一遍，當 R 有十八位數時這完全沒希望。數位動態規劃改成一次填一位、由左而右地建出數，並一筆就數完一整族的完成方式。訣竅在於一個小小的狀態，它總結了「後面的選擇需要知道的、關於目前前綴的一切」——而且不多不少。
這個狀態通常有三部分：你正在填的位置；一個「貼界」旗標，表示目前的前綴是否恰好和 R 的前綴一模一樣（這會限制下一位的上限，因為填得更高就會超過 R）；以及問題所需的任何性質累加器（例如目前的數字和對 7 取模、前一位數字等等）。計數 [L, R] 接著用 F(R) - F(L-1) 完成，其中 F(X) 數的是 [0, X] 裡合格的數。回報非常可觀：你走訪的不是 R+1 個數，而是大約（位數）乘以（少數幾個性質狀態）乘以（10 種數字選擇）——關於位數是多項式的，不是指數的。
期望值型動態規劃與線性性質這份禮物
現在把同一張表對準隨機性。一個期望值型動態規劃問的是：如果過程會做出隨機的移動，某個結果的「期望」值是多少——平均的步數、平均的分數、最終獲勝的機率？狀態依然總結了「你在哪裡」，但每個表格項現在裝的是一個期望值，而轉移式則用機率對隨機的移動取平均。如果從狀態 s 以機率 p 走到狀態 a、以機率 1-p 走到狀態 b，且兩種走法都付出一步，那麼 `E[s] = 1 + p*E[a] + (1-p)*E[b]`。那個加權和是整個主題的主力。
我們憑什麼可以就這樣對子節點的期望值取平均？因為期望值的線性性質：對任何隨機變數（即使彼此相依）都有 E[X + Y] = E[X] + E[Y]。它讓我們把「期望的總步數」拆成「這一步（值 1）加上期望的剩餘步數」，而期望的剩餘步數本身又是子節點期望值的加權平均——這恰好就是上面那條轉移式。線性性質是讓期望值型動態規劃能運作的沉默夥伴，也正是在隨機演算法那一階，賦予隨機快速排序 O(n log n) 期望時間的同一個工具。
這裡有一個計數時不會出現的真正細節。當隨機過程可能繞回來——你也許會在抵達終點前重訪某個狀態——方程式就變得相互依賴，像 `E[s] = 1 + p*E[s] + (1-p)*E[done]` 這樣，E[s] 同時出現在等號兩邊。這就不再是單純的自底向上填表了：你必須用代數解出 E[s]（這裡把同類項收一收後得到 E[s] = 1/(1-p) + ...），而一團這樣的方程式就成了一個線性方程組。樸素的製表法假設依賴是一張無環的有向無環圖；有環的期望值打破了這個假設，需要靠代數、或靠迭代的數值求解。
同一張有向無環圖，三種讀法
退一步看，這份統一性令人印象深刻。最佳化、計數、期望值是「同一張」子問題的依賴有向無環圖，以同樣的拓樸順序求值；不同的只是把一個狀態的子節點合併起來的那個運算。最佳化用最小值或最大值合併；計數用加號合併（並留意不相交性）；期望值用機率加權的平均合併（並留意環）。這正是為什麼精通其中一個，幾乎可以整套地遷移到另外兩個——定義狀態和證明子結構這些苦工是共用的，被換掉的只有最後那一個代數步驟。
optimize: f[s] = OPT over choices c of ( value(c) + f[next(s,c)] ) # OPT = min or max count: f[s] = SUM over choices c of ( f[next(s,c)] ) % MOD # choices must be disjoint expectation: f[s] = SUM over choices c of ( prob(c) * f[next(s,c)] ) + local_cost
兩個誠實的收尾提醒，因為這份對稱性可能讓你鬆懈。第一，漸進分析描述的依然是「規模如何放大」，而不是在每個尺寸上的判決：同一個狀態空間上的計數型動態規劃和最佳化動態規劃共用相同的大O，但隱藏常數不同——模乘法比整數比較更貴——所以別把相等的大O讀成相等的實際時間。第二，每種風味的正確性義務確實不同：最佳化需要最佳子結構、計數需要選擇彼此不相交、期望值需要把環的結構處理好。借用對的轉移式形狀，並不讓你能跳過「你的狀態滿足它那種風味的前提」這個證明。