對于不能劃分階段的問題，不能用動态規劃來解；對于能劃分階段，但不符合最優化原理，也不能用動态規劃來解；既能劃分階段，又符合最優化原理，但不具備無後效性原則的，還是不能用動态規劃來解；誤用動态規劃程式設計方法求解會導緻錯誤的結果。
有什麼樣的問題它不滿足最優子結構？
如果一個問題的最優解包含其子問題的最優解，我們就稱此問題具有最優子結構。
如果用"白"一點的話說。定義一個問題 Ｑ，求目标解 Ａ。如果我們找出的目标解 A 的同時， Q 的子問題的目标解同時也被找到，那麼稱問題 Ｑ 具有最優子結構。
舉個簡單的例子。下面是一個地圖，我們要找一條從左下角（起點）到右上角（終點）、隻向右和向上走的路徑。
| -1 | -2 | +1 |
| +3 | -4 | +1 |
| -1 | +2 | -2 |
| +2 | -2 | +1 |
如果要讓路徑經過的數字總和最大，那麼最優路徑是下面這條：
可以驗證，對于最優路徑上的任意一點，最優路徑從起點到該點的部分，也正是從起點到該點的所有路徑中數字總和最大的那一條。這就叫「滿足最優子結構」。
現在換一個「最優」的标準，要求路徑經過的數字總和的絕對值最小。那麼最優路徑是下面這條：
但是，對于最優路徑上 -4 這個點，最優路徑從起點到該點的部分，卻不是從起點到該點的所有路徑中，數字總和的絕對值最小的那一條，因為下面這條路徑上數字總和的絕對值更小：
這就叫「不滿足最優子結構」。
常見的最優化問題，問法一般都是「最大」「最小」，不太會出現「絕對值最小」這種奇葩的最優化标準。而問「最大」「最小」的問題，一般都是滿足最優子結構的。
最優子結構的目标函數一般都具有“單調性”。而諸如絕對值，模值這種的目标函數就不具有最優子結構。
也可以直接看書上一個典型的反例，有向圖中求最長簡單路徑。
此例顯示了無權有向圖最長簡單路徑問題不具有最優子結構性質。路徑q→r→t是從q到t的一條最長簡單路徑，但q→r不是從q到r的一條最長簡單路徑，r→t同樣不是從r到t的一條最長簡單路徑。
”最優子結構“的描述并不隻适用于求最優解問題。比如求解斐波那契數列問題、比如求有向無環圖中指定節點之間的路徑數問題，比如面試中常提到的上台階問題，在字面上是不太容易歸結到"最優“。
是以在描述中使用的是，目标解 A，而不是最優解 Ａ。
所謂無後效性原則，指的是這樣一種性質：某階段的狀态一旦确定，則此後過程的演變不再受此前各狀态及決策的影響。也就是說，“未來與過去無關”，目前的狀态是此前曆史的一個完整總結，此前的曆史隻能通過目前的狀态去影響過程未來的演變。具體地說，如果一個問題被劃分各個階段之後，階段k+1中的狀态隻能通過階段k中的狀态通過狀态轉移方程得來，與其他狀态沒有關系，特别是與未發生的狀态沒有關系，這就是無後效性。
無後效性是動态規劃算法及貪心算法的前提條件無後效性：某階段的狀态一旦确定，則此後過程的決策不再受此前各種狀态及決策的影響。有後效性：就是某個狀态之後要做的決策會受之前的狀态及決策的影響。
如下圖有四乘四的網格，要從左上角走的右下角，條件是每次隻能向下或向右走。如下圖從起點走到黑色圓圈位置S(2,2)有兩種方案，但是S(2,2)接下來所做的決策不用考慮之前的決策，故是無後效性。如果把條件改為：可以往前後左右走但是不能走重複的格子，那麼接下來要做的決策就需要考慮之前的決策，故此時是有後效性。
ref
https://www.zhihu.com/question/52165201
https://baike.baidu.com/item/無後效性/1135283?fr=aladdin
-End-