(HDUACM)動(dòng)態(tài)規(guī)劃分析

ACM程序設(shè)計(jì)杭州電子科技大學(xué)劉春英acm@10/14/2024111月份比賽你嗎？報(bào)名了10/14/20242每周一星（4）：BlackGanglion10/14/20243知識(shí)回顧遞推求解...10/14/20244第五講動(dòng)態(tài)規(guī)劃（Dynamicprogramming）10/14/20245一、經(jīng)典問題：數(shù)塔問題

有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。10/14/20246用暴力的方法，可以嗎？10/14/20247 這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如31），則需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目（2^30=1024^3>10^9=10億）。試想一下：10/14/20248

拒絕暴力，倡導(dǎo)和諧～10/14/20249

從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。 同樣，下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時(shí)就非常明了。 如數(shù)字2，只要選擇它下面較大值的結(jié)點(diǎn)19前進(jìn)就可以了。所以實(shí)際求解時(shí)，可從底層開始，層層遞進(jìn)，最后得到最大值。

結(jié)論：自頂向下的分析，自底向上的計(jì)算?？紤]一下：10/14/202410思考：免費(fèi)餡餅

10/14/202411如何解決？請(qǐng)發(fā)表見解

10/14/202412威威貓系列故事——打地鼠

再思考：10/14/202413二、經(jīng)典問題：最長有序子序列10/14/202414解決方案：10/14/202415思考

1160FatMouse'sSpeed

SampleInput

6008130060002100

5002000100040001100300060002000800014006000120020001900SampleOutput

4459710/14/202416再思考（1087期末考試題）SuperJumping!Jumping! Juping!

10/14/202417解題思路？10/14/202418三、經(jīng)典問題：最長公共子序列HDOJ-1159：SampleInput

abcfbcabfcab

programmingcontest

abcdmnpSampleOutput

4

2

010/14/202419輔助空間變化示意圖10/14/202420f(i,j)=

{由于f(i,j)只和f(i-1,j-1),f(i-1,j)和f(i,j-1)有關(guān),而在計(jì)算f(i,j)時(shí),只要選擇一個(gè)合適的順序,就可以保證這三項(xiàng)都已經(jīng)計(jì)算出來了,這樣就可以計(jì)算出f(i,j).這樣一直推到f(len(a),len(b))就得到所要求的解了.f(i-1,j-1)+1(a[i]==b[j])max(f(i-1,j),f(i,j-1))(a[i]!=b[j])

子結(jié)構(gòu)特征：10/14/202421四、經(jīng)典問題：1421

搬寢室

SampleInput

21

13

SampleOutput

410/14/202422第一感覺：根據(jù)題目的要求，每次提的兩個(gè)物品重量差越小越好，是不是每次提的物品一定是重量相鄰的物品呢？證明：假設(shè)四個(gè)從小到大的數(shù)：a、b、c、d，只需證明以下表達(dá)式成立即可：(a-b)^2+(c-d)^2<(a-c)^2+(b-d)^2(a-b)^2+(c-d)^2<(a-d)^2+(b-c)^2……(略)10/14/202423預(yù)備工作：排序！10/14/202424第二感覺：對(duì)于一次操作，顯然提的物品重量越接近越好，是不是可以貪心呢？請(qǐng)思考…考慮以下情況： 1458什么結(jié)論？10/14/202425詳細(xì)分析：從最簡單的情況考慮：2個(gè)物品選一對(duì)，結(jié)論顯然結(jié)論？4個(gè)物品選一對(duì)？（如何利用前面的知識(shí)）3個(gè)物品選一對(duì)，…n個(gè)物品選一對(duì)，…最終問題：n個(gè)物品選k對(duì)，如何？（n>=2k）n個(gè)物品選二對(duì)，…10/14/202426五、經(jīng)典問題：1058HumbleNumbers

ProblemDescriptionAnumberwhoseonlyprimefactorsare2,3,5or7iscalledahumblenumber.Thesequence1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,...showsthefirst20humblenumbers.

Writeaprogramtofindandprintthenthelementinthissequence10/14/202427算法分析：典型的DP!1->?1->2=min(1*2,1*3,1*5,1*7)1->2->3=min(2*2,1*3,1*5,1*7)1->2->3->4=min(2*2,2*3,1*5,1*7)1->2->3->4->5=min(3*2,2*3,1*5,1*7)10/14/202428狀態(tài)轉(zhuǎn)移方程？F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7) (n>i,j,k,m)特別的： i,j,k,m只有在本項(xiàng)被選中后才移動(dòng)10/14/202429

如果各個(gè)子問題不是獨(dú)立的，不同的子問題的個(gè)數(shù)只是多項(xiàng)式量級(jí)，如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要的時(shí)候再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算。

由此而來的基本思路是——用一個(gè)表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果