動態規劃的兩個前提條件

在動手用動態規劃之前，值得先問一個簡單的問題：這個問題真的是動態規劃能攻克的嗎？有兩個方格都必須打勾。第一，最佳子結構：整體的最佳答案由較小片段的最佳答案組成。第二，重疊子問題：這些較小片段會反覆出現——同一個小問題被一問再問。當兩者都成立時，動態規劃就是對的工具；當任一個失效時，你就需要別的方法。

為什麼要兩個，而不是只要一個？最佳子結構給你一條遞迴關係式——一種用較小答案表達原答案的方式——使得正確的遞迴解根本存在。重疊子問題則讓這條遞迴值得做快取：若小答案會反覆出現，把每個都存起來重用，就能把指數級的爆炸壓回多項式的工作量。若你有最佳子結構卻沒有重疊（如合併排序，其兩半互不相交），單純的分治法就已足夠，記憶表只是浪費空間。若你有重疊卻沒有最佳子結構（如最長簡單路徑），那麼你要記憶化的遞迴本身就是錯的，於是快取只是加速了一個給出錯誤答案的計算。

在實作上，這份檢查表就是你的設計紀律。問自己：我能否把最佳解表達成「一個選擇，加上一個剩餘子問題的最佳解」（子結構）？以及：是否只會出現多項式個相異的子問題，且每個都被需要許多次（重疊）？若兩者皆是，就定義狀態、寫出轉移、設好基底情況、選定計算順序，你就有了一個動態規劃。若有子結構但每個子問題都獨一無二，那你面對的其實是分治問題。這兩個前提條件不是官僚式的方格——它們恰恰是保證一個動態規劃既正確又快速的東西。