引言：本人在做過一些題目後對dp有些感想，就寫了這個總結：
第一節動態規劃基本概念
一，動態規劃三要素：階段，狀態，決策。
他們的概念到處都是，我就不多說了，我只說說我對他們的理解：
如果把動態規劃的求解過程看成乙個工廠的生產線，階段就是生產某個商品的不同的環節，狀態就是工件當前的形態，決策就是對工件的操作。顯然不同階段是對產品的乙個前面各個狀態的小結，有乙個個的小結構成了最終的整個生產線。每個狀態間又有關聯（下乙個狀態是由上乙個狀態做了某個決策後產生的）。
下面舉個例子：
要生產一批雪糕，在這個過程中要分好多環節：購買牛奶，對牛奶提純處理，放入工廠加工，加工後的商品要包裝，包裝後就去銷售……，這樣沒個環節就可以看做是乙個階段；產品在不同的時候有不同的狀態，剛開始時只是白白的牛奶，進入生產後做成了各種造型，從冷凍庫拿出來後就變成雪糕（由液態變成固態=_=||）。每個形態就是乙個狀態，那從液態變成固態經過了冰凍這一操作，這個操作就是乙個決策。
乙個狀態經過乙個決策變成了另外乙個狀態，這個過程就是狀態轉移，用來描述狀態轉移的方程就是狀態轉移方程。
經過這個例子相信大家對動態規劃有所了解了吧。
下面在說說我對動態規劃的另外乙個理解：
用圖論知識理解動態規劃：把動態規劃中的狀態抽象成乙個點，在有直接關聯的狀態間連一條有向邊，狀態轉移的代價就是邊上的權。這樣就形成了乙個有向無環圖aoe網（為什麼無環呢？
往下看）。對這個圖進行拓撲排序，刪除乙個邊後同時出現入度為0的狀態在同一階段。這樣對圖求最優路徑就是動態規劃問題的求解。
二，動態規劃的適用範圍
動態規劃用於解決多階段決策最優化問題，但是不是所有的最優化問題都可以用動態規劃解答呢？
一般在題目中出現求最優解的問題就要考慮動態規劃了，但是否可以用還要滿足兩個條件：
最優子結構（最優化原理）
無後效性
最優化原理在下面的最短路徑問題中有詳細的解答；
什麼是無後效性呢？
就是說在狀態i求解時用到狀態j而狀態j就解有用到狀態k…..狀態n。
而求狀態n時有用到了狀態i這樣求解狀態的過程形成了環就沒法用動態規劃解答了，這也是上面用圖論理解動態規劃中形成的圖無環的原因。
也就是說當前狀態是前面狀態的完美總結，現在與過去無關。。。
當然，有是換乙個劃分狀態或階段的方法就滿足無後效性了，這樣的問題仍然可以用動態規劃解。
三，動態規劃解決問題的一般思路。
拿到多階段決策最優化問題後，第一步要判斷這個問題是否可以用動態規劃解決，如果不能就要考慮搜尋或貪心了。當卻定問題可以用動態規劃後，就要用下面介紹的方法解決問題了：
（1）模型匹配法：
最先考慮的就是這個方法了。挖掘問題的本質，如果發現問題是自己熟悉的某個基本的模型，就直接套用，但要小心其中的一些小的變動，現在考題辦都是基本模型的變形套用時要小心條件，三思而後行。這些基本模型在先面的分類中將一一介紹。
（2）三要素法
仔細分析問題嘗試著確定動態規劃的三要素，不同問題的卻定方向不同：
先確定階段的問題：數塔問題，和走路問題（詳見解題報告）
先確定狀態的問題：大多數都是先確定狀態的。
先確定決策的問題：揹包問題。（詳見解題報告）
一般都是先從比較明顯的地方入手，至於怎麼知道哪個明顯就是經驗問題了，多做題就會發現。
（3）尋找規律法：
這個方法很簡單，耐心推幾組資料後，看他們的規律，總結規律間的共性，有點貪心的意思。
（4）邊界條件法
找到問題的邊界條件，然後考慮邊界條件與它的領接狀態之間的關係。這個方法也很起效。
（5）放寬約束和增加約束
這個思想是在陳啟鋒的**裡看到的，具體內容就是給問題增加一些條件或刪除一些條件使問題變的清晰。
第二節動態規劃分類討論
這裡用狀態維數對動態規劃進行了分類：
1.狀態是一維的
1．1下降/非降子串行問題：
問題描述：
在乙個無序的序列a1,a2,a3,a4…an裡，找到乙個最長的序列滿足：ai<=aj<=ak…<=am,且iaj>ak…>am,且i>j>k…>m.（最長下降子串行）。
問題分析：
如果前i-1個數中用到ak (ak>ai或ak<=ai)構成了乙個的最長的序列加上第i個數ai就是前i個數中用到i的最長的序列了。那麼求用到ak構成的最長的序列有要求前k-1個數中……
從上面的分析可以看出這樣劃分問題滿足最優子結構，那滿足無後效性麼？顯然對於第i個數時只考慮前i-1個數,顯然滿足無後效性，可以用動態規劃解。
分析到這裡動態規劃的三要素就不難得出了：如果按照序列編號劃分階段，設計乙個狀態opt[i] 表示前i個數中用到第i個數所構成的最優解。那麼決策就是在前i-1個狀態中找到最大的opt[j]使得aj>ai(或aj<=ai)，opt[j]+1就是opt[i]的值；用方程表示為：
opt[i]=max(opt[j])+1 (0<=jopt[i]=max(opt[j])+1 (0<=jai)
實現求解的部分**：
opt[0]:=maxsize；
for i:=1 to n do
for j:=0 to i-1 do
if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if opt[i]>ans then ans:=opt[i];
複雜度：從上面的實現不難看出時間複雜度為o（n2），空間複雜度o（n）；
[, , ] (missile.pas/c/cpp) **：noip1999(提高組) 第一題
【問題描述】
某國為了防禦敵國的飛彈襲擊，發展出一種飛彈攔截系統。但是這種飛彈攔截系統有乙個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。
某天，雷達捕捉到敵國的飛彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的飛彈。
輸入飛彈依次飛來的高度（雷達給出的高度資料是不大於30000的正整數），計算這套系統最多能攔截多少飛彈，如果要攔截所有飛彈最少要配備多少套這種飛彈攔截系統。
【輸入檔案】missile.in
單獨一行列出飛彈依次飛來的高度。
【輸出檔案】missile.out
兩行，分別是最多能攔截的飛彈數，要攔截所有飛彈最少要配備的系統數
【輸入樣例】
389 207 155 300 299 170 158 65
【輸出樣例】62
【問題分析】
有經驗的選手不難看出這是乙個求最長非公升子串行問題，顯然標準演算法是動態規劃。
以飛彈依次飛來的順序為階段，設計狀態opt[i]表示前i個飛彈中攔截了飛彈i可以攔截最多能攔截到的飛彈的個數。
狀態轉移方程：
opt[i]=max(opt[j])+1 (h[i]>=h[j],0=最大的opt[i]就是最終的解。
這只解決了第一問，對於第二問最直觀的方法就是求完一次opt[i]後把剛才要打的飛彈去掉，在求一次opt[i]直到打完所有的飛彈，但這樣做就錯了。
不難舉出反例： 6 1 7 3 2
錯解： 6 3 2/1/7 正解：6 1/7 3 2
其實認真分析一下題就回發現：每乙個飛彈最終的結果都是要被打的，如果它後面有乙個比它高的飛彈，那打它的這個裝置無論如何也不能打那個飛彈了，經過這麼一分析，這個問題便抽象成在已知序列裡找最長上公升序列的問題。
求最長上公升序列和上面說的求最長非公升序列是一樣的，這裡就不多說了。
複雜度：時間複雜度為o（n2），空間複雜度為o（n）。
【源**】
program missile;
const
fin='missile.in';
fout='missile.out';
maxn=10000;
vara,opt:array[0..maxn] of longint;
n,anslen,anstime:longint;
procedure init;
varx:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
n:=0;
repeat
inc(n);
read(a[n]);
until seekeof;
end;
procedure main;
vari,j:longint;
begin
fillchar(opt,sizeof(opt),0);
a[0]:=maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]>=a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
anslen:=0;
for i:=1 to n do
if opt[i]>anslen then
anslen:=opt[i];
fillchar(opt,sizeof(opt),0);
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]opt[i]) then
opt[i]:=opt[j]+1;
anstime:=0;
for i:=1 to n do
if opt[i]>anstime then
anstime:=opt[i];
end;
procedure print;
begin
writeln(anslen);
writeln(anstime);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
[, , ] (chorus.pas/c/cpp) **：noip2004(提高組) 第一題
n位同學站成一排，**老師要請其中的(n-k)位同學出列，使得剩下的k位同學排成合唱隊形。
合唱隊形是指這樣的一種隊形：設k位同學從左到右依次編號為1，2…，k，他們的身高分別為t1，t2，…，tk，則他們的身高滿足t1<...ti+1>…>tk(1<=i<=k)。
動態規劃經典教程完整版 好
引言 本人在做過一些題目後對dp有些感想，於是寫了這個總結 第一節動態規劃基本概念 一，動態規劃三要素 階段，狀態，決策。他們的概念到處都是，我就不多說了，我只說說我對他們的理解 如果把動態規劃的求解過程看成乙個工廠的生產線，階段就是生產某個商品的不同的環節，狀態就是工件當前的形態，決策就是對工件的...
Flash經典教程
1.2熟悉flash的工作環境 要建立動畫，使用者首先要了解它的工作環境，了解一些基本的概念，如舞台，圖層，幀與關鍵幀。本節主要介紹這方面的情況。啟動flash，並在 開始 頁中選擇一項進行，就可進入flash的工作環境。如下圖，flash8.0的工作介面，主要有舞台，主工具欄，工具箱，時間軸，屬性...
PROE經典教程
親愛的朋友們 大家好！在當今這個時代，社會各行各業競爭都很激烈。能夠掌握一技之長在社會上立足實在非常重要！一方面我們要生存！另一方面我們要更好的生活！只有不斷進取！不斷努力！才能立於不敗之地！才能跟上時代步伐！創造美好生活！慶幸我們能夠選擇工業產品設計這個大行業，這個行業在任何時代都不會淘汰。但是，...