定義動態規劃的狀態
每個動態規劃都建立在一個寫任何程式碼之前就要下的設計決定上：子問題到底是什麼，我又該如何為它命名？答案就是狀態——一小束數值，精確地釘住一個子問題，並作為查表的鍵。把它選好就完成了大半工作；狀態一旦對了，遞迴通常自然浮現，狀態一旦錯了，再聰明的程式碼也救不了你。把狀態想成你那格表格所回答的問題，寫得完整到兩個不同的格子永遠不可能代表同一件事。
好的狀態有兩個性質。它必須充分：它捕捉了情境中一切會影響最佳化未來走向的資訊，使得最佳的後續只依賴於狀態，而不依賴隱藏的歷史。它也應該最小：不攜帶任何無關的細節，因為每多一個維度都會讓狀態數倍增，從而拉長執行時間。以 0/1 背包為例，你可能定義 dp[i][w] = 只用前 i 件物品、容量為 w 時可達的最佳總價值。這個對 (i, w) 是充分的——給定它，未來的選擇不在乎你先前具體拿了哪幾件，只在乎還剩多少容量——而且是最小的，因為去掉任一座標都會讓不同情境相撞。
相異狀態的個數乘上算出其中一個的工作量，就是執行時間，所以狀態設計正是你的動態規劃成本被決定之處。這也是你讓問題變得可解或無望的地方：狀態定得不夠（漏掉一個未來會依賴的參數）會給出錯誤答案，因為相異子問題被混為一談；狀態定得過頭（多了一個你並不需要的維度）雖正確卻徒然變慢或耗記憶體。許多進階動態規劃的功夫，就在於找到一個剛好豐富到正確、又剛好精簡到快速的狀態。
對最長遞增子序列，定義 dp[i] = 恰以索引 i 結尾的最長遞增子序列長度。「以 i 結尾」這句話使狀態充分：它固定了最後一個元素，於是 dp[i] 可由較早的 j（滿足 a[j] < a[i]）的 dp[j] 建出。若把 dp[i] 只定義成「使用前 i 個元素」，狀態就太弱——轉移無法判斷 a[i] 能否延伸某個給定的子序列。
對的狀態恰好固定了足夠的東西（此處是最後一個元素），讓未來只依賴於狀態。
若你的轉移需要某個狀態並未記錄的過去事實，那狀態就定義不足，將給出錯誤答案——去修狀態，而不是用旁路資料去補轉移。