1、第四講動態規劃（Dynamic programming）2022/7/271一、經典問題：數塔問題 有形如下圖所示的數塔，從頂部出發，在每一結點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。2022/7/272用暴力的方法，可以嗎？2022/7/273這道題如果用枚舉法（暴力思想），在數塔層數稍大的情況下（如31），則需要列舉出的路徑條數將是一個非常龐大的數目（230= 10243 109=10億）。試想一下：2022/7/274 拒絕暴力，倡導和諧2022/7/275從頂點出發時到底向左走還是向右走應取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道

2、路徑上的最大值求出來了才能作出決策。同樣，下一層的走向又要取決于再下一層上的最大值是否已經求出才能決策。這樣一層一層推下去，直到倒數第二層時就非常明了。如數字2，只要選擇它下面較大值的結點19前進就可以了。所以實際求解時，可從底層開始，層層遞進，最后得到最大值。結論：自頂向下的分析，自底向上的計算。考慮一下：2022/7/276思路：從倒數第二行起， 按照狀態轉移方程dpij = max(dpi + 1j, dpi + 1j + 1) + valij向上遞推， 直到val11， 此時dp11就是結果2022/7/277二、經典問題：最長有序子序列問題描述 找出由n個元素組成的序列的最長有序子序

3、列長度及其中一個最長有序子序列（注：這里有序指非遞減順序，且不要求子序列連續）。例如，對于序列3, 7, 1, 5, 9, 3，其中最長有序子序列長度為3，這樣的子序列有：3, 7, 9、1, 5, 9、3, 5, 9。 2022/7/278二、經典問題：最長有序子序列2022/7/279二、經典問題：最長有序子序列2022/7/2710二、經典問題：最長有序子序列2022/7/2711三 1160 FatMouses Speed Problem DescriptionFatMouse believes that the fatter a mouse is, the faster it run

4、s. To disprovethis, you want to take the data on a collection of mice and put as large asubset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.InputInput contains data for a bunch of mice, one mouse per line, terminated byend of file.The dat

5、a for a particular mouse will consist of a pair of integers: the firstrepresenting its size in grams and the second representing its speed incentimeters per second. Both integers are between 1 and 10000. The data ineach test case will contain information for at most 1000 mice.Two mice may have the s

6、ame weight, the same speed, or even the sameweight and speed.2022/7/2712三 1160 FatMouses Speed OutputYour program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse).

7、If these n integers are m1, m2,., mn then it must be the case thatWm1 Wm2 . Sm2 . SmnIn order for the answer to be correct, n should be as large as possible.All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for

8、 a given input, your program only needs to find one.2022/7/2713三 1160 FatMouses Speed Sample Input6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 Sample Output4 4 5 9 72022/7/2714三 1160 FatMouses Speed 解題思路：題目要求找到的體重遞增，速度遞減老鼠，先把老鼠的體重進行升序排序然后算出速度的最長遞減子序列。 2022

9、/7/2715四 1087 Super Jumping! Jumping!Juping! Problem DescriptionNowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now. The game can be played by two or more than two pla

10、yers. It consists of a chessboard（棋盤）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jum

11、ps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. O

12、f course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path.Your task is to output the maximum value according to the given chessme

13、n list.2022/7/2716四 1087 Super Jumping! Jumping!Juping!InputInput contains multiple test cases. Each test case is described in a line as follow:N value_1 value_2 value_NIt is guarantied that N is not more than 1000 and all value_i are in the range of 32-int.A test case starting with 0 terminates the

14、 input and this test case is not to be processed.OutputFor each case, print the maximum according to rules, and one line one case.2022/7/2717四 1087 Super Jumping! Jumping!Juping!Sample Input3 1 3 2 4 1 2 3 4 4 3 3 2 1 0Sample Output4 10 32022/7/2718解題思路？找序列中最大升序子序列的和 2022/7/2719動態規劃算法與分治法類似，其基本思想也是將

15、待求解問題分解成若干個子問題算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2022/7/2720但是經分解得到的子問題往往不是互相獨立的。不同子問題的數目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2022/7/2721如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從

16、而得到多項式時間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)2022/7/2722動態規劃基本步驟找出最優解的性質，并刻劃其結構特征。遞歸地定義最優值。以自底向上的方式計算出最優值。根據計算最優值時得到的信息，構造最優解。2022/7/2723動態規劃算法的基本要素一、最優子結構 問題的最優解包含著其子問題的最優解。這種性質稱為最優子結構性質。在分析問題的最優子結構性質時，所用的方法具有普遍性：首先假設由問題的最優解導出的子問題的解不是最優的，然后再設法

17、說明在這個假設下可構造出比原問題最優解更好的解，從而導致矛盾。 利用問題的最優子結構性質，以自底向上的方式遞歸地從子問題的最優解逐步構造出整個問題的最優解。最優子結構是問題能用動態規劃算法求解的前提。同一個問題可以有多種方式刻劃它的最優子結構，有些表示方法的求解速度更快（空間占用小，問題的維度低）2022/7/2724動態規劃算法的基本要素二、重疊子問題遞歸算法求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質。動態規劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數時間查看一下結果。 通常不同的

18、子問題個數隨問題的大小呈多項式增長。因此用動態規劃算法只需要多項式時間，從而獲得較高的解題效率。 2022/7/2725動態規劃算法的基本要素三、備忘錄方法備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。int LookupChain(int i，int j) if (mij 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int

19、k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u;2022/7/2726五、經典問題：最長公共子序列Problem DescriptionA subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = another seque

20、nce Z = is a subsequence of X if there exists a strictly increasing sequence of indices of X such that for all j = 1,2,.,k, xij = zj. For example, Z = is a subsequence of X = with index sequence . Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence

21、of X and Y.The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the m

22、aximum-length common subsequence from the beginning of a separate line.2022/7/2727五、經典問題：最長公共子序列HDOJ-1159：Sample Inputabcfbc abfcabprogramming contest abcd mnp Sample Output 4 2 02022/7/2728最長公共子序列若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個嚴格遞增下標序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，

23、B，C，B，D，A，B的子序列，相應的遞增下標序列為2，3，5，7。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 2022/7/2729最長公共子序列的結構設序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。(2)若xmyn且zkxm，則Z是xm-1和Y的最長公共子序列。(3)若xmyn且zkyn，則Z是X和yn-1的最長公共子序列。由

24、此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優子結構性質。 2022/7/2730子問題的遞歸結構由最長公共子序列問題的最優子結構性質建立子問題最優值的遞歸關系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其它情況下，由最優子結構性質可建立遞歸關系如下：2022/7/2731abcfbca111111b122222f122333c123334a123334b123344輔助空間變化示意圖2022/7/2732計

25、算最優值由于在所考慮的子問題空間中，總共有(mn)個不同的子問題，因此，用動態規劃算法自底向上地計算最優值能提高算法的效率。 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 構造最長公共子序列void LCS(in

26、t i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b);2022/7/2733算法的改進在算法lcsLength和lcs中，可進一步將數組b省去。事實上，數組元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個數組元素的值所確定。對于給定的數組元素cij，可以不借助于數組b而僅借助于c本身在時間內確定cij的值是由ci-1j-1，ci-1j和cij-1中哪一個值

27、所確定的。如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減少。事實上，在計算cij時，只用到數組c的第i行和第i-1行。因此，用2行的數組空間就可以計算出最長公共子序列的長度。進一步的分析還可將空間需求減至O(min(m,n)。2022/7/2734六、經典問題：1421 搬寢室Problem Description 搬寢室是很累的,xhd深有體會.時間追述2019年7月9號,那天xhd迫于無奈要從27號樓搬到3號樓,因為10號要封樓了.看著寢室里的n件物品,xhd開始發呆,因為n是一個小于2000的整數,實在是太多了,于是xhd決定隨便搬2*k件過去就行了.但還是會很累,因為2*

28、k也不小是一個不大于n的整數.幸運的是xhd根據多年的搬東西的經驗發現每搬一次的疲勞度是和左右手的物品的重量差的平方成正比(這里補充一句,xhd每次搬兩件東西,左手一件右手一件).例如xhd左手拿重量為3的物品,右手拿重量為6的物品,則他搬完這次的疲勞度為(6-3)2 = 9.現在可憐的xhd希望知道搬完這2*k件物品后的最佳狀態是怎樣的(也就是最低的疲勞度),請告訴他吧.2022/7/2735六、經典問題：1421 搬寢室Input每組輸入數據有兩行,第一行有兩個數n,k(2=2*k=n2000).第二行有n個整數分別表示n件物品的重量(重量是一個小于215的正整數).Output對應每組輸

29、入數據,輸出數據只有一個表示他的最少的疲勞度,每個一行.2022/7/2736六、經典問題：1421 搬寢室Sample Input 2 1 1 3Sample Output 42022/7/2737第一感覺：根據題目的要求，每次提的兩個物品重量差越小越好，是不是每次提的物品一定是重量相鄰的物品呢？證明：假設四個從小到大的數：a、b、c、d，只需證明以下表達式成立即可：(a-b)2+(c-d)2 (a-c)2+(b-d)2(a-b)2+(c-d)2=2k） ，如何？n個物品選二對，2022/7/2741解題思路先對物品的重量進行排序，取相鄰的物品，將相鄰的物品的差的平方另外存儲，得到狀態轉移方

30、程：dpij=min(dpi-1j,dpi-2j-1+si),si是代表i,i+1這兩個物品的疲憊度.因為si-1,si.代表的是ai-1,ai,ai+1的疲憊度，中間共享了一個ai，所以第二項要用dpi-2.2022/7/2742參考代碼#include#includeusingnamespacestd;#defineINF0 x7fffffffintdp20002000,a2000,s2000;intmain()intn,k,i,j;while(scanf(%d%d,&n,&k)!=EOF)for(i=1;i=n;i+)scanf(%d,&ai);sort(a,a+n+1);for(i=1

31、;i=n;i+)for(j=1;j=n/2;j+)dpij=INF;for(i=2;i=n;i+)si=(ai-ai-1)*(ai-ai-1);for(i=2;i=n;i+)for(j=1;j=i/2;j+)dpij=min(dpi-1j,dpi-2j-1+si);printf(%dn,dpnk);return0;2022/7/2743七、經典問題：1058 Humble NumbersProblem Description A number whose only prime factors are 2,3,5 or 7 is called a humble number. The seque

32、nce 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, . shows the first 20 humble numbers. Write a program to find and print the nth element in this sequence 2022/7/2744七、經典問題：1058 Humble NumbersInputThe input consists of one or more test cases. Each test case consists of one integer n with 1 = n ?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)2022/7/2747狀態轉移方程？F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7)(ni,j,k,m)特別的：i,j,k,m