1樓：Tanki Zhang
先回顧下動態規劃問題的求解過程：
（1）證明該問題具有最優子結構性質(區域性最優解能決定全域性最優解)；
（2）根據最優子結構，求遞推方程；
（3）根據遞推方程，說明該問題具有重疊子結構性質；
（4）自底向上寫出求解最優值的非遞迴演算法，同時構造最優解的解空間樹；
（5）遍歷解空間樹，求得最優解。
貪心演算法是求乙個子問題的解，假設這個解是子問題的最優解，在此基礎上再進一步推導更大問題的最優解。
這意味著，「貪心演算法最後求出解是最優的」是基於「子問題的解的確是最優的」並且「全域性最優 該區域性最優解」。如果這一點不成立，那貪心最後的結果也並不可靠。
再回過頭來看動態規劃，由於在求解時，第一步就要求要證明最優子結構，所以保證了「全域性最優 該區域性最優解」。
綜上，回答題主問題，是通過證明最優子結構來證明的。感覺題主有這個問題是因為很多時候大家都是說感覺這個可以dp解，然後就dp了，如果不是有必要，大家不會很嚴肅的推導，或者在推導遞推方程的時候，很自然就承認了的確存在最優子結構這件事。
最後，隨便找了個揹包問題的最優子結構證明。
2樓：冒泡
如何理解動態規劃？
基本上你可以理解為，在暴力搜尋的基礎上減掉了一些重複計算，從而加快速度，正確性和暴力搜尋的結果是一樣的，而後者由於列舉了所有可能情況，所以必然是得到最優結果的
3樓：
比方說整數值的揹包問題，表示狀態的物品index-總容量對上有乙個典範的良序（就是你列舉狀態的順序了）。假設這個演算法在某個input下不對，取出最小的狀態座標，使得求解出的這個子問題答案錯誤。根據假設它的前繼子問題都是求解正確的，帶入bellman方程，它也應該被算對，矛盾。
稍微一般一點的情況就是在狀態的DAG上做歸納但是題主想問的應該不是這個問題，而是「怎麼確認一種子問題劃分和相應的狀態轉移方程是正確的」，這個問題就太meta了可能不太好回答。。
在你設計出乙個dp演算法之前往往會考慮一些樸素的暴力方法，列舉原問題「完整的action序列」，優化目標是這個action序列上的可能比較複雜的某個函式。這個objective往往寫成有限步的計算，所有的中間結果都是有序域\mathbb上的元素。有的時候你會發現action序列的某些部分在計算的某一部開始不再被用到了，被用到的只是這些action在之前參與的某（幾）個中間計算結果。
由於\mathbb上常見的操作在每個位置上都有良好的單調性，很可能能找到一組中間結果，使得我們能夠列舉這種中間結果來完成原問題的優化
動態規劃的最優子結構問題，有什麼樣的問題它不滿足最優子結構？
最典型的就是求最長路了。給定乙個帶權無向圖，起點，終點，要求每個節點只能訪問一次，求從起點到終點的最長路。參考求最短路的過程，把求最短路的過程套在求最長路上，按照求最短路的方式構建的子結構來推最長路，會遇到什麼問題？可能會出現節點被重複訪問的情況，這是不符合題意的。 鄧卓 如果乙個問題的最優解包含其...
「得到APP」的使用者都是一類什麼樣的人？
麥子 得到的使用者我覺得社會的各個階層的人都有在上面，比如我乙個上班族，也是會把除了上班之外的大部分時間都用在得到課程上面。我覺得除了工作之外，我可以獲得的知識和開闊視野的機會太少了。去線下的培訓班又不太現實，正好得到上的課程包羅永珍，從日常生活 職場關係 歷史 金融.都有，基本上就滿足了我的需求了...
世界上的問題真的只有一種最優解嗎？乙個事物可以有絕對的正誤嗎？
外向的孤獨患者 一道數學題可以有很多解題方法，我們先設定最簡潔的解法就是最優。那很多數學題都有多個最優的解法 兩個解法都只需要兩步，那就都是最優的。這是第乙個問題。 星辰明月你 我覺得不是。看了其他兩個人的回答，恕不能苟同。就好像解題，一道題有很多種演算法，老師列了4種，並告訴我們其中一種步驟簡單思...