重疊子問題（overlapping subproblems）

想像你在爬樓梯，有人問你到達第 10 階共有幾種走法，每步可以上一階或兩階。要回答第 10 階，你需要第 9 階和第 8 階的答案；可是要回答第 9 階，你又得用到第 8 階和第 7 階。第 8 階的答案就這樣從不同方向一再被需要。如果你每次都從頭重算，就會做大量重複的工作。這種對同一批小答案反覆的需求，就是我們所說的重疊子問題。

更精確地說，當一個直接的遞迴解法在把問題拆成更小的片段時，反覆解到同一個小片段，這個問題就具有重疊子問題。誠實的檢驗方法是畫出遞迴樹（哪個呼叫產生哪些呼叫的圖），看看同一個呼叫是否在多處出現。計算第 n 個費氏數時，fib(n) 呼叫 fib(n-1) 與 fib(n-2)；fib(n-1) 又呼叫 fib(n-2) 與 fib(n-3)；於是 fib(n-2) 已被需要兩次，fib(n-3) 三次，重複量像滾雪球般擴大。這裡相異的子問題其實只有約 n 個（fib(0) 到 fib(n) 這些值），但天真的遞迴卻會做出大約 2^n 次呼叫。其中幾乎全是重算。

這正是動態規劃所利用的破口。關鍵洞見是去數相異的子問題，而不是數遞迴呼叫的總數：若相異子問題只有多項式個，但呼叫卻有指數個，那麼把每個相異子問題只算一次並存起答案，就能把指數時間的演算法變成多項式時間。請注意它與合併排序這類分治法的對比：在合併排序中，子問題落在互不重疊的兩半上，永不重疊——那裡做快取毫無好處，因為每個呼叫都確實是全新的。