動態規劃水演算法題

Ⅰ 演算法題套路總結（三）——動態規劃

前兩篇我總結了鏈表和二分查找題目的一些套路，這篇文章來講講動態規劃。動態規劃從我高中開始參加NOIP起就一直是令我比較害怕的題型，除了能一眼看出來轉移方程的題目，大部分動態規劃都不太會做。加上後來ACM更為令人頭禿的動態規劃，很多題解看了之後，我根本就不相信自己能夠想出來這種解法，看著大佬們談笑間還加一些常數優化，一度懷疑自己的智商。以前一直覺得動態規劃是給大佬准備的，所以刻意地沒有去攻克它，主要也是沒有信心。但是後來慢慢的，我再做LC的時候，發現很多DP的題目我自己慢慢能夠推出轉移方程了，而且似乎也沒那麼難。我一直在思考，到底是我變強了，還是因為LC的題目相比ACM或者NOI太簡單了。其實主要還是後者，但是同時我也發現，動態規劃其實是有套路的，我以前方法不對，總結太少。
主要就是，站在出題人的角度，他幾乎不太可能完全憑空想出一個新的DP模型，因為動態規劃畢竟要滿足：

因此，能夠利用DP來解決的問題實際上是有限的，大部分題目都是針對現有的模型的一些變種，改改題目描述，或者加點限制條件。所以要想攻克DP題目，最根本的就是要充分理解幾個常見的DP模型。而要充分理解常見經典DP模型，就需要通過大量的做題和總結，而且二者不可偏廢。通過做題進行思考和量的積累，通過總結加深理解和融會貫通進而完成質的提升。

動態規劃是求解一個最優化問題，而最核心的思想就是：

解一道DP題目，先問自己幾個問題：

當然以上內容看起來比較抽象，雖然它深刻地揭露了動態規劃的本質，但是如果臨場要去想明白這些問題，還是有些難度。如果只是針對比賽和面試，就像前面說的，DP題型是有限的。只要刷的題目足夠多，總結出幾個經典模型，剩下的都是些變種+優化而已。

一般來說，動態規劃可以分成4個大類:

線性DP就是階段非常線性直觀的模型，比如：最長（上升|下降）序列，最長公共子序列(LCS)等，也有一些簡單的遞推，甚至都算不上是 經典模型 。

最長上升序列是一個非常經典的線性模型。說它是個模型，是因為它是一類題的代表，很多題目都只是換個說法，或者要求在這基礎上進一步優化而已。最長上升序列最基礎的轉移方程就是 f[i] = max{f[j]}+1 (a[i] > a[j]) , f[i] 表示一定要以 a[i] 結尾的序列，最長長度是多少。很顯然就是在前面找到一個最大的 f[j] 同時滿足 a[j]<a[i] 。因此是 N^2 的時間復雜度和N的空間復雜度。這種方法是最樸素直觀的，一定要理解。它非常簡單，因此很少有題目直接能夠這么做。大部分相關題目需要進一步優化，也就是有名的單調隊列優化，能夠把復雜度優化到nlogn。

說單調隊列優化之前必須明白一個貪心策略。因為要求的是最長上升序列，那麼很顯然長度為k的上升序列的最大值（最後一個數）越小越好，這樣後面的數才有更大的概率比它大。如果我們記錄下來不同長度的上升序列的最後一個數能達到的最小值，那麼對於後續每個數t，它要麼能放到某個長度為y的序列之後，組成長度為y+1的上升序列，要麼放到某個長度為x的序列後面，把長度為x+1的序列的最大值替換成t。同時我們可以發現，如果x<y，那麼長度為x序列的最後一個數一定比長度為y的序列最後一個數小。因此這個上升序列我們可以用一個數組來維護（所謂的單調隊列），數組下標就代表序列長度。 opt[i]=t 表示長度為i的上升序列最後一個數最小是t。那麼當我們在面對後續某個數x時，可以對單調隊列opt進行二分，把它插到對應的位置。因此總體復雜度就是NlogN。
相關題目比如：

但是你可以發現，其實這個題型其實變種很有限，吃透了也就那麼回事。所以一定要總結。

最長公共子序列也是線性DP中的一種比較常見的模型。說它是一種「模型」其實有點拔高了，其實它就是一類比較常見的題目。很多題目都是在LCS的基礎上進行簡單的擴展，或者僅僅就是換一個說法而已。
求兩個數組的最長公共子序列，最直觀地做法就是：設f[i][j]表示S[..i]和T[..j]的最長公共子序列，則有:

這個轉移方程也非常好理解，時間復雜度是 N^2 ，空間復雜度也是 N^2 。不過仔細觀察你可以發現，當我們計算第i行時只與i-1和i行有關。因此我們可以利用01滾動來優化空間復雜度為2N。
相關題目：

線性DP除了上述的兩種常見題型，還有很多別的類型，包括背包。我們要努力去嘗試理解這些題目的異同，它們的轉移方程，以及思路，可能的變化，這樣才能更好的應對未知的題目。以下是一些我總結的題型：

最終結果就是max(0, f[n][2]+f[n][4])。
不過實際上你可以發現，由於各個狀態只和前一維有關，且只能由固定的一個狀態轉移過來，因此我們可以省掉一維，只用4個變數來存儲：

剩下的，同123題類似，由於最多進行k次交易，那麼一天就有2k個狀態：第1次買/賣……第k次買/賣，結合123題的優化，我們只需要2k個變數就能存儲這些狀態。因此設f[i×2]為第i次買入的最優值，f[i×2+1]為第i次賣出的最優值：

以上都是對一些常見的線性DP的一些小結，實際上線性DP還有一個重要的題型就是背包。關於背包，有很多相關的講解，我這里就不多說了，推薦大家看看 背包九講 。下一章依然是DP專題，我講總結一些區間DP的題型。大部分區間DP都是hard級的，對於希望提高自己水平的人來說，需要投入更多精力去理解。

Ⅱ 動態規劃演算法建模，3 名商人各帶 1 名隨從乘船渡河問題

①1商人1僕人坐船 商人乘船回
②商人下船 2僕人坐船 1僕人乘船回
③僕人下船 2商人坐船 1商人1僕人乘船回
④僕人下船 2商人坐船 1僕人乘船回
至此3個商人全部到達河對岸 讓1僕人把剩下兩個僕人拉過對岸來就好了。。

Ⅲ 動態規劃演算法的題目（急）

給出個思路吧：
階段變數i：1~n門課程
狀態變數h：已經用掉的小時數h
決策變數dh：下一門課程分配的小時數dh
目標函數sum_f：已經在前i門課上取得的總成績sum_f
狀態轉移方程：sum_f(i+1)=sum_f(i)+f(i+1)
順時序遞推計算即可.

Ⅳ 1、 用動態規劃方法求下述問題的最優解：Max z=x1x2x3x4 2x1+3x2+x3+2x4=11Xj≥0且為整數

偶形式： 2y1-y2-y3=-2 3y1-2y2-3y3=-4 求 max -24y1+10y2+15y3 優解 y1=0,y2=2,y3=0 優值20設原始問題min{cx|Ax=bx≥0}則其偶問題 max{yb|yA≤c}。

原問題引入人工變數x4，剩餘變數x5，人工變數x6 。

maxz=2x1+3x2-5x3 -mx4-mx6、x1+x2+x3+x4=7，2x1-5x2+x3-x5+x6=10,x1,x2,x3，x4，x5，x6≥0用人工變數法求解。

大m法：先化成標准形

max z'＝-2x1-3x2-x3+0x4+0x5-Mx6-Mx7

s.t. x1+4x2+2x3-x4+x6＝4

3x1+2x2-x5+x7＝6

x1 x2 x3 x4 x5 x6 x7≥0

最優解 X＝（4/5,9/5,0,0,0,0）

Z最優值 min z＝7

非基變數x3的檢驗數等於0，所以有無窮多最優解

兩階段法：第一階段最優解X＝(4/5,9/5,0,0,0,0)是基本可行解 min z＝0

第二階段最優解 X＝（4/5,9/5,0,0,0,0） min z＝7

非基變數x3的檢驗數為0，所以有無窮多最優解

(4)動態規劃水演算法題擴展閱讀：

動態規劃演算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。動態規劃演算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。

若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。

Ⅳ 動態規劃演算法程序例子

給你導彈攔截的吧：
[問題描述]
某國為了防禦敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈依次飛來的高度（雷達給出的高度數據是不大於30000的正整數，每個數據之間至少有一個空格），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。

[輸入輸出樣例]
INPUT：
389 207 155 300 299 170 158 65
OUTPUT：
6（最多能攔截的導彈數）
2（要攔截所有導彈最少要配備的系統數）

[問題分析]
我們先解決第一問。一套系統最多能攔多少導彈，跟它最後攔截的導彈高度有很大關系。假設a[i]表示攔截的最後一枚導彈是第i枚時，系統能攔得的最大導彈數。例如，樣例中a[5]=3，表示：如果系統攔截的最後一枚導彈是299的話，最多可以攔截第1枚（389）、第4枚（300）、第5枚（299）三枚導彈。顯然，a[1]~a[8]中的最大值就是第一問的答案。關鍵是怎樣求得a[1]~a[8]。
假設現在已經求得a[1]~a[7]（註：在動態規劃中，這樣的假設往往是很必要的），那麼怎樣求a[8]呢？a[8]要求系統攔截的最後1枚導彈必須是65，也就意味著倒數第2枚被攔截的導彈高度必須不小於65，則符合要求的導彈有389、207、155、300、299、170、158。假如最後第二枚導彈是300，則a[8]=a[4]+1；假如倒數第2枚導彈是299，則a[8]=a[5]+1；類似地，a[8]還可能是a[1]+1、a[2]+1、……。當然，我們現在求得是以65結尾的最多導彈數目，因此a[8]要取所有可能值的最大值，即a[8]=max{a[1]+1,a[2]+1,……，a[7]+1}=max{a[i]}+1 (i=1..7)。
類似地，我們可以假設a[1]~a[6]為已知，來求得a[7]。同樣，a[6]、a[5]、a[4]、a[3]、a[2]也是類似求法，而a[1]就是1，即如果系統攔截的最後1枚導彈是389，則只能攔截第1枚。
這樣，求解過程可以用下列式子歸納：
a[1]=1
a[i]=max{a[j]}+1 （i>1，j=1,2,…,i-1，且j同時要滿足：a[j]>=a[i]）
最後，只需把a[1]~a[8]中的最大值輸出即可。這就是第一問的解法，這種解題方法就稱為「動態規劃」。

第二問比較有意思。由於它緊接著第一問，所以很容易受前面的影響，多次採用第一問的辦法，然後得出總次數，其實這是不對的。要舉反例並不難，比如長為7的高度序列「7 5 4 1 6 3 2」， 最長不上升序列為「7 5 4 3 2」，用多次求最長不上升序列的結果為3套系統；但其實只要2套，分別擊落「7 5 4 1」與「6 3 2」。所以不能用「動態規劃」做，那麼，正確的做法又是什麼呢？
我們的目標是用最少的系統擊落所有導彈，至於系統之間怎麼分配導彈數目則無關緊要，上面錯誤的想法正是承襲了「一套系統盡量多攔截導彈」的思維定勢，忽視了最優解中各個系統攔截數較為平均的情況，本質上是一種貪心演算法，但貪心的策略不對。如果從每套系統攔截的導彈方面來想行不通的話，我們就應該換一個思路，從攔截某個導彈所選的系統入手。
題目告訴我們，已有系統目前的瞄準高度必須不低於來犯導彈高度，所以，當已有的系統均無法攔截該導彈時，就不得不啟用新系統。如果已有系統中有一個能攔截該導彈，我們是應該繼續使用它，還是另起爐灶呢？事實是：無論用哪套系統，只要攔截了這枚導彈，那麼系統的瞄準高度就等於導彈高度，這一點對舊的或新的系統都適用。而新系統能攔截的導彈高度最高，即新系統的性能優於任意一套已使用的系統。既然如此，我們當然應該選擇已有的系統。如果已有系統中有多個可以攔截該導彈，究竟選哪一個呢？當前瞄準高度較高的系統的「潛力」較大，而瞄準高度較低的系統則不同，它能打下的導彈別的系統也能打下，它夠不到的導彈卻未必是別的系統所夠不到的。所以，當有多個系統供選擇時，要選瞄準高度最低的使用，當然瞄準高度同時也要大於等於來犯導彈高度。
解題時用一個數組sys記下當前已有系統的各個當前瞄準高度，該數組中實際元素的個數就是第二問的解答。

[參考程序]
program noip1999_2;
const max=1000;
var i,j,current,maxlong,minheight,select,tail,total:longint;
height,longest,sys:array [1..max] of longint;
line:string;
begin
write('Input test data:');
readln(line); {輸入用字元串}
i:=1;
total:=0; {飛來的導彈數}
while i<=length(line) do {分解出若干個數，存儲在height數組中}
begin
while (i<=length(line)) and (line[i]=' ') do i:=i+1; {過濾空格}
current:=0; {記錄一個導彈的高度}
while (i<=length(line)) and (line[i]<>' ') do {將一個字元串變成數}
begin
current:=current*10+ord(line[i])-ord('0');
i:=i+1
end;
total:=total+1;
height[total]:=current {存儲在height中}
end;
longest[1]:=1; {以下用動態規劃求第一問}
for i:=2 to total do
begin
maxlong:=1;
for j:=1 to i-1 do
begin
if height[i]<=height[j]
then if longest[j]+1>maxlong
then maxlong:=longest[j]+1;
longest[i]:=maxlong {以第i個導彈為結束，能攔截的最多導彈數}
end;
end;
maxlong:=longest[1];
for i:=2 to total do
if longest[i]>maxlong then maxlong:=longest[i];
writeln(maxlong); {輸出第一問的結果}
sys[1]:=height[1]; {以下求第二問}
tail:=1; {數組下標，最後也就是所需系統數}
for i:=2 to total do
begin
minheight:=maxint;
for j:=1 to tail do {找一套最適合的系統}
if sys[j]>height[i] then
if sys[j]<minheight then
begin minheight:=sys[j]; select:=j end;
if minheight=maxint {開一套新系統}
then begin tail:=tail+1; sys[tail]:=height[i] end
else sys[select]:=height[i]
end;
writeln(tail)
end.

[部分測試數據]
輸入1：300 250 275 252 200 138 245
輸出1：
5
2

輸入2：181 205 471 782 1033 1058 1111
輸出2：
1
7

輸入3：465 978 486 476 324 575 384 278 214 657 218 445 123
輸出3：
7
4

輸入4：236 865 858 565 545 445 455 656 844 735 638 652 659 714 845
輸出4：
6
7
夠詳細的吧

Ⅵ 問一道動態規劃演算法題. 設A和B是長度相等,長度為n的字元串. 他們的最長公共子串長度為(n-L)

最長公共子序列（Longest-Common-Subsequence，LCS）
dp[i][j]：dp[i][j]表示長度分別為i和j的序列X和序列Y構成的LCS的長度
dp[i][j] = 0，如果i=0 或 j=0
dp[i][j] = dp[i-1][j-1] + 1，如果 X[i-1] = Y[i-1]
dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }，如果 X[i-1] != Y[i-1]
LCS長度為 dp[Xlen][Ylen]

Ⅶ 動態規劃法的原理

動態規劃法[dynamic programming method (DP)]是系統分析中一種常用的方法。在水資源規劃中,往往涉及到地表水庫調度、水資源量的合理分配、優化調度等問題,而這些問題又可概化為多階段決策過程問題。動態規劃法是解決此類問題的有效方法。動態規劃法是20世紀50年代由貝爾曼（R. Bellman）等人提出,用來解決多階段決策過程問題的一種最優化方法。所謂多階段決策過程,就是把研究問題分成若干個相互聯系的階段,由每個階段都作出決策,從而使整個過程達到最優化。許多實際問題利用動態規劃法處理,常比線性規劃法更為有效,特別是對於那些離散型問題。實際上,動態規劃法就是分多階段進行決策,其基本思路是：按時空特點將復雜問題劃分為相互聯系的若干個階段,在選定系統行進方向之後,逆著這個行進方向,從終點向始點計算,逐次對每個階段尋找某種決策,使整個過程達到最優,故又稱為逆序決策過程。
[1]動態規劃的基本思想
前文主要介紹了動態規劃的一些理論依據，我們將前文所說的具有明顯的階段劃分和狀態轉移方程的動態規劃稱為標准動態規劃，這種標准動態規劃是在研究多階段決策問題時推導出來的，適合用於理論上的分析。在實際應用中，許多問題的階段劃分並不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規模更小的子問題，並且原問題的最優解中包含了子問題的最優解（即滿足最優子化原理），則可以考慮用動態規劃解決。
動態規劃的實質是分治思想和解決冗餘，因此，動態規劃是一種將問題實例分解為更小的、相似的子問題，並存儲子問題的解而避免計算重復的子問題，以解決最優化問題的演算法策略。
由此可知，動態規劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，並通過求解子問題產生一個全局最優解。其中貪心法的當前選擇可能要依賴已經作出的所有選擇，但不依賴於有待於做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的（即不包含公共的子子問題），因此一旦遞歸地求出各子問題的解後，便可自下而上地將子問題的解合並成問題的解。但不足的是，如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題。
解決上述問題的辦法是利用動態規劃。該方法主要應用於最優化問題，這類問題會有多種可能的解，每個解都有一個值，而動態規劃找出其中最優（最大或最小）值的解。若存在若干個取最優值的解的話，它只取其中的一個。但是首先要保證該問題的無後效性,即無論當前取哪個解,對後面的子問題都沒有影響.在求解過程中，該方法也是通過求解局部子問題的解達到全局最優解，但與分治法和貪心法不同的是，動態規劃允許這些子問題不獨立，（亦即各子問題可包含公共的子子問題）也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，並將結果保存起來，避免每次碰到時都要重復計算。
因此，動態規劃法所針對的問題有一個顯著的特徵，即它所對應的子問題樹中的子問題呈現大量的重復。動態規劃法的關鍵就在於，對於重復出現的子問題，只在第一次遇到時加以求解，並把答案保存起來，讓以後再遇到時直接引用，不必重新求解。
3、動態規劃演算法的基本步驟
設計一個標準的動態規劃演算法，通常可按以下幾個步驟進行：
（1）劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的（即無後向性），否則問題就無法用動態規劃求解。
（2）選擇狀態：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。

Ⅷ 動態規劃演算法詳解

動態規劃一般也只能應用於有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解(對有些問題這個要求並不能完全滿足，故有時需要引入一定的近似)。簡單地說，問題能夠分解成子問題來解決。

將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解（這部分與分治法相似）。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到的子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。通常可以用一個表來記錄所有已解的子問題的答案。

問題的一個最優解中所包含的子問題的解也是最優的。總問題包含很多個子問題，而這些子問題的解也是最優的。

用遞歸演算法對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重復計算多次。問題重疊性質是指在用遞歸演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重復計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率。

：很顯然，這道題的對應的數學表達式是

其中F(1)=1, F(2)=2。很自然的狀況是，採用遞歸函數來求解：

參考：
http://blog.csdn.net/zmazon/article/details/8247015
http://blog.csdn.net/lisonglisonglisong/article/details/41548557
http://blog.csdn.net/v_JULY_v/article/details/6110269
http://blog.csdn.net/trochiluses/article/details/37966729

Ⅸ 動態規劃演算法（pascal）

在計算夠不夠開銷時
20%這個數據是廢的
你可以先減去預算再考慮存多少錢
比如手頭錢的數目為a
預算為b
存在媽媽處的錢為c
可以先從a中減去b
然後c就等於c+a
div
100
*100
var
略
begin
a:=0;
c:=0;
bo:=true;
for
i:=1
to
12
do
begin
read(b[i]);
inc(a,300);
if
a<b[i]
then
begin
writeln(i);
bo:=false;
break;
end
else
begin
c:=c+a
div
100*100;
dec(a,b[i]);
a:=a
mod
100;
end;
end;
if
bo
then
writeln(a+c+c
div
5);
end.