動態規劃的最優子結構問題，有什麼樣的問題它不滿足最優子結構？

1樓：

最典型的就是求最長路了。給定乙個帶權無向圖，起點，終點，要求每個節點只能訪問一次，求從起點到終點的最長路。

參考求最短路的過程，把求最短路的過程套在求最長路上，按照求最短路的方式構建的子結構來推最長路，會遇到什麼問題？

可能會出現節點被重複訪問的情況，這是不符合題意的。

2樓：鄧卓

如果乙個問題的最優解包含其子問題的最優解，我們就稱此問題具有最優子結構。

演算法導論，15.3 動態規劃原理

如果用"白"一點的話說。

定義乙個問題Ｑ，求目標解Ａ。如果我們找出的目標解 A 的同時， Q 的子問題的目標解同時也被找到，那麼稱問題Ｑ具有最優子結構。

舉的例子， @王贇 Maigo 答案通俗易懂。也可以直接看書上乙個典型的反例，有向圖中求最長簡單路徑。

這裡額外提一句，雖然叫做」最優子結構「，但是這條描述並不只適用於求最優解問題。比如求解斐波那契數列問題、比如求有向無環圖中指定節點之間的路徑數問題，比如面試中常提到的上台階問題，在字面上是不太容易歸結到"最優「。

所以在描述中使用的是，目標解 A，而不是最優解Ａ。

3樓：

普通無向圖的最長路因為有環，然而可以找dag上的最長路。最優子結構腦補一下就是給定乙個偏序集P和定義在上面的函式F，a in P and b in P，aF(a) < F(b)。所以解這樣的問題要找到這樣的偏序集（往往不太好找），和這樣的F，那麼F的最大（小）值一定在偏序集的上（下）界取得。

4樓：Chen Boss

組合問題其實分兩類：排列問題和組合問題。題主說的最優子結構大概指的是最優子集問題（例如：揹包問題，頂點覆蓋問題）。排列問題（例如排序）什麼的嚴格來說不是最優子集問題。

5樓：王贇 Maigo

舉個簡單的例子。下面是乙個地圖，我們要找一條從左下角（起點）到右上角（終點）、只向右和向上走的路徑。

如果要讓路徑經過的數字總和最大，那麼最優路徑是下面這條：

可以驗證，對於最優路徑上的任意一點，最優路徑從起點到該點的部分，也正是從起點到該點的所有路徑中數字總和最大的那一條。這就叫「滿足最優子結構」。

現在換乙個「最優」的標準，要求路徑經過的數字總和的絕對值最小。那麼最優路徑是下面這條：

但是，對於最優路徑上 -4 這個點，最優路徑從起點到該點的部分，卻不是從起點到該點的所有路徑中，數字總和的絕對值最小的那一條，因為下面這條路徑上數字總和的絕對值更小：

這就叫「不滿足最優子結構」。

常見的最優化問題，問法一般都是「最大」「最小」，不太會出現「絕對值最小」這種奇葩的最優化標準。而問「最大」「最小」的問題，一般都是滿足最優子結構的。

6樓：zhpmatrix

zhpmatrix.github.io/201

6/10/08/dynamic-programming/

)，明白之後重新思考這個問題可能比較合適。