建議先看看前言：http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
這一節(jié)可以看到《算法導(dǎo)論》學(xué)習(xí)總結(jié) — 16.第15章 動(dòng)態(tài)規(guī)劃(1) 基本入門的補(bǔ)充。
采用動(dòng)態(tài)規(guī)劃的最優(yōu)化問題的兩個(gè)要素：最優(yōu)子結(jié)構(gòu)和重疊子問題。
先看看最優(yōu)子結(jié)構(gòu)：
在第17篇總結(jié)時(shí)，裝配線調(diào)度問題中，已經(jīng)設(shè)計(jì)到了最優(yōu)子結(jié)構(gòu)，證明最優(yōu)子結(jié)構(gòu)問題可以用書上說的“剪貼技術(shù)”，即假設(shè)存在更優(yōu)的解，來反正最優(yōu)解矛盾。
再看看重疊子問題：
當(dāng)一個(gè)遞歸算法不斷的調(diào)用同一個(gè)問題時(shí)，我們說該最有問題包含“重疊子問題”。
上面這句話不好理解？
看看下面這個(gè)比較：
遞歸算法：自頂而下，對(duì)在遞歸樹中重復(fù)出現(xiàn)的每個(gè)子問題都要重復(fù)解一次。
動(dòng)態(tài)規(guī)劃：自下而上，對(duì)每個(gè)只解一次。
結(jié)合第16篇總結(jié)的三角形求值例子，可以看得到，自下而上導(dǎo)致每個(gè)子問題只求解一次。
以上理論性有點(diǎn)強(qiáng)，我最開始學(xué)DP看的是HDOJ的課件，有興趣的可以去看看。
在那里面，主要講到了是找狀態(tài)轉(zhuǎn)移方程，在第16篇的三角形求值例子和第17篇的裝配線調(diào)度例子，那些遞歸公式都是狀態(tài)轉(zhuǎn)移方程。
下面這段話好好理解：
——————————————————————–
動(dòng)態(tài)規(guī)劃的幾個(gè)概念:
階段：據(jù)空間順序或時(shí)間順序?qū)栴}的求解劃分階段。
狀態(tài)：描述事物的性質(zhì)，不同事物有不同的性質(zhì)，因而用不同的狀態(tài)來刻畫。對(duì)問題的求解狀態(tài)的描述是分階段的。
決策：根據(jù)題意要求，對(duì)每個(gè)階段所做出的某種選擇性操作。
狀態(tài)轉(zhuǎn)移方程：用數(shù)學(xué)公式描述與階段相關(guān)的狀態(tài)間的演變規(guī)律。
動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，是解決多階段決策過程最優(yōu)化的一種方法。
所謂多階段決策過程，是將所研究的過程劃分為若干個(gè)相互聯(lián)系的階段，在求解時(shí)，對(duì)每一個(gè)階段都要做出決策，前一個(gè)決策確定以后，常常會(huì)影響下一個(gè)階段的決策。
動(dòng)態(tài)規(guī)劃所依據(jù)的是“最優(yōu)性原理”。
“最優(yōu)性原理”可陳述為：不論初始狀態(tài)和第一步?jīng)Q策是什么，余下的決策相對(duì)于前一次決策所產(chǎn)生的新狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。
最優(yōu)決策序列的子序列，一定是局部最優(yōu)決策子序列。
包含有非局部最優(yōu)的決策子序列，一定不是最優(yōu)決策序列。
動(dòng)態(tài)規(guī)劃的指導(dǎo)思想是：
在做每一步?jīng)Q策時(shí)，列出各種可能的局部解，之后依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解。這樣，在每一步都經(jīng)過篩選，以每一步都是最優(yōu)的來保證全局是最優(yōu)的。篩選相當(dāng)于最大限度地有效剪枝（從搜索角度看），效率會(huì)十分高。但它又不同于貪心法。貪心法只能做到局部最優(yōu)，不能保證全局最優(yōu)，因?yàn)橛行﹩栴}不符合最優(yōu)性原理。
——————————————————————–
看見有人說遞歸就是DFS，而DP就是BFS，感覺有那么一點(diǎn)意思，對(duì)于DP，就是從底層一層層的計(jì)算，然后在當(dāng)層中選取最優(yōu)，逐層最優(yōu)以至總體最優(yōu)。
其實(shí)這個(gè)還是多做一些題就好了(⊙ｏ⊙)，大家別認(rèn)為我是做題控，其實(shí)說實(shí)在話，看N遍不如做一題，說白了，算法數(shù)學(xué)本一家，算法就是數(shù)學(xué)，走過高中的，都知道數(shù)學(xué)題得多做，尤其壓軸題，看N遍不如做一遍，這個(gè)也是一樣做幾題就知道DP是神馬東東了！