動態(tài)規(guī)劃 (dp) 是一種思想，并不一定要用來求解最優(yōu)值（最大值或最小值），而且能夠用來求解滿足某種約束的答案。甚至高中階段用到的排列組合其實就是動態(tài)規(guī)劃一種。斐波那契數(shù)列是一個典型的 線性dp 問題。動態(tài)規(guī)劃所說的 「最優(yōu)子結(jié)構(gòu)」就是問題能夠分解為若干子問題，這些子問題可能存在重疊，然后就是子問題最優(yōu)的時候原問題也一定最優(yōu)。然后「后無效性」是說，動態(tài)規(guī)劃的狀態(tài)頂點之間，在邏輯上面是一個 『DAG 結(jié)構(gòu)』，這是一個圖，一個有向無環(huán)圖（如果你覺得把邏輯結(jié)構(gòu)想象為一個圖有點抽象，可以嘗試想想一些二分查找的過程邏輯上面等價于一個樹），如果邏輯上面有環(huán)則將涉及一系列的破環(huán)技巧，比如插頭 DP 等等。然后 up 提到 動態(tài)規(guī)劃是一個帶緩存的分治算法，這個觀點是不對的，動態(tài)規(guī)劃確實用到分治思想，但它與我們通過所說的『分治算法』有一點不一樣，分治算法邏輯上面是一棵樹，同一層的子問題是沒有交集的，但是動態(tài)規(guī)劃的子問題是一個有向無環(huán)圖，是存在大量重疊的子問題的。然后最后up 提到的「這種方法叫做狀態(tài)壓縮」也是不對的，「狀態(tài)壓縮」是一種位運算技巧，此處用到的優(yōu)化技巧叫做 「滾動數(shù)組」，不知道 up 是不是受到了 labuladong 影響，labuladong 有一篇高閱讀量的題解提到了錯把這個方法稱為「狀態(tài)壓縮」，但是這種稱呼是一個謬傳，而且labuladong大部分的題解來自于 USA 力扣翻譯，里面很多東西可能 labuladong 也不理解。