計數動態規劃（counting DP）

大多數入門動態規劃在最佳化某個東西——最短路徑、最大價值、最少硬幣。計數動態規劃則回答「有幾種？」：有幾種鋪磚方式、穿過格子有幾條路徑、有幾個字串避開某個禁用模式。結構與最佳化動態規劃相同，但合併子問題的運算改變了。最佳化動態規劃在各選擇上取 min 或 max，計數動態規劃則取「和」，因為做一件事的方法數，是各個互斥的第一步的方法數之和。

從最佳化通往計數的橋樑建立在兩條組合規則上。加法規則：若一個最終結果可經由幾個互斥的情況達成，它的計數是各情況計數之和——這就是轉移要相加的原因。乘法規則：若一個構造是一個獨立的前半部接著一個獨立的後半部，計數就是兩部分計數之積。所以計數轉移通常長成 dp[state] = 在每個有效的前一狀態上對 dp[前一狀態] 求和（若某一步有數個獨立的子選擇，再乘上一個重數因子）。例如，計數格子中只能向右或向下走的路徑：dp[i][j] = dp[i-1][j] + dp[i][j-1]，因為進入格子 (i, j) 的每條路徑不是從上方就是從左方來，而那兩組路徑互斥，所以相加。基底 dp[0][0] = 1 表示在起點恰有一種「空」的方式。

計數動態規劃與對應的最佳化動態規劃有相同的時間與空間成本——唯一的改變是用「加／求和」取代「min／max」——所以它繼承結構所允許的任何加速法（前綴和等）。有兩個專屬於計數的誠實提醒。第一，計數可能大得驚人（常呈指數成長），所以答案通常要求對某個質數如 10^9 + 7 取模，且你必須邊算邊取模以避免溢位。第二，正確性取決於各情況真正互斥且窮盡：若兩種不同的狀態拆解方式會產生「同一個」物件，你就重複計數了；若某些物件不屬於任何情況，你就少算了。把劃分弄得恰到好處——每個物件恰好被算一次——正是計數動態規劃真正的細微之處。