動(dòng)態(tài)規(guī)劃問題整理

1、動(dòng)態(tài)規(guī)劃：【1】.矩陣乘法鏈，最小乘法次數(shù)。一、問題描述給定一個(gè)矩陣序列，計(jì)算乘積A1A2An。要求找出一個(gè)加全部括號(hào)的方式，使得標(biāo)量乘法的次數(shù)最小。對(duì)于任意兩個(gè)矩陣AiAi+1相乘，其乘法次數(shù)為pi-1pi pi+1，不同的加全部括號(hào)，所需要的乘法次數(shù)可能相差很大。假設(shè)現(xiàn)在有三個(gè)矩陣A1A2A3相乘，維數(shù)分別為：10100，1005，550。1、如果我們采用如下方式加全部括號(hào)：(（A1A2）A3)則首先計(jì)算（A1A2），乘法次數(shù)為p0p1 p2，得到新矩陣的維數(shù)為p0 p2計(jì)算(（A1A2）A3)，乘法次數(shù)為p0p2 p3，總的計(jì)算次數(shù)為p0p1 p2+ p0p2 p3=101005+105

2、50=75002、如果我們采用如下方式加全部括號(hào)：(A1（A2 A3）)則首先計(jì)算（A2 A3），乘法次數(shù)為p1 p2 p3，得到新矩陣的維數(shù)為p1 p3計(jì)算(A1（A2 A3）)，乘法次數(shù)為p0p1 p3，總的計(jì)算次數(shù)為p1 p2 p3+ p0p1 p3=100550+1010050=75000第二種方式需要的次數(shù)是第二次的10倍！二、問題分析：由前面可知，一個(gè)序列如果只有一個(gè)矩陣，則只有一種方式加全部括號(hào)，如果有兩個(gè)或兩個(gè)以上的矩陣，則必然可以看做兩個(gè)子序列的乘積，且這兩個(gè)子序列也是加全部括號(hào)。我們用cost(i,j)表示序列AiAj在最優(yōu)加全部括號(hào)時(shí)的標(biāo)量乘積次數(shù)，則其中p(i-1)p(

3、k) p(j)為子序列AiAk與Ak+1Aj相乘時(shí)的標(biāo)量相乘次數(shù)。順序連城可以把最后一個(gè)單個(gè)的看成單獨(dú)加括號(hào)。三、問題求解每一對(duì)滿足1ijn的i和j都對(duì)應(yīng)原問題的一個(gè)子問題，子問題個(gè)數(shù)為動(dòng)態(tài)規(guī)劃（二）：矩陣鏈乘法，其中第一項(xiàng)表示i=i的部分，且valueii=0。動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)步驟如下：步驟一：令step=0；步驟二：對(duì)于所有i=0，n，計(jì)算并保存valueii+step；步驟三：若step=n-1，則結(jié)束，否則step=step+1，返回步驟二。矩陣維數(shù)A13035A23515A3155A4510A51020A62025/實(shí)現(xiàn)思想：1.令step不同，即（j-i）不同；2.從i到j(luò)選擇不同的

4、分割點(diǎn)k。i = k j；求出極大值。記錄分割的位置。三重循環(huán)，從底層開始；首先分析：step=1，得到組合(1,2)、(2,3)、（3,4）、（4,5）、（5,6）；step=2，得到組合(1,3)、(2,4)、（3,5）、（4,6）；而其中，step=2，要用到不同的k了。（1,2）3或者1（2,3）；同理step=3，得到組合(1,4)、(2,5)、（3,6）；要用到不同的k了。1（2,3,4）或者（1,2）（3，4）或者（1,2,3）4；這些都是step為小的時(shí)候得到的。最終得到的step=5，得到組合（1,6）。才是我們需要的。【2】.裝配線調(diào)度問題?，F(xiàn)有兩條裝配線，Sij表示第i條

5、上完成第j道工序的裝配站。汽車完成組裝需要依次完成1n工序。請(qǐng)找出完成裝配并離開裝配線的最快路線。符號(hào)說明：ei：汽車進(jìn)入裝配線i的時(shí)間，i=1,2xi：汽車離開裝配線i的時(shí)間aij：在裝配站Sij完成裝配需要的時(shí)間tij：在裝配站Sij完成后離開第i條裝配線，進(jìn)入另一條裝配線需要的轉(zhuǎn)移時(shí)間注意，如果完成工序后，下一個(gè)工序還在同一條裝配線上，則不需要轉(zhuǎn)移時(shí)間。問題求解：用Fij表示在第i條裝配線上完成第j道工序的最快時(shí)間，用F表示完成汽車裝配并離開裝配線的時(shí)間，如果知道F1n和F2n，則有：要求出F1n和F2n，需要知道F1n-1和F2n-1，則有故得到遞推公式：2、動(dòng)態(tài)規(guī)劃如果我們不是從上到

6、下求解，而是從下到上求解，求解結(jié)果在某個(gè)地方保存起來，則可以大大改善求解速度。這里的動(dòng)態(tài)min只有兩個(gè)部分，只有一個(gè)存在遞歸的形式，而上面哪一個(gè)卻又兩個(gè)遞歸的部分。/ 同理遞增也是一樣的，動(dòng)態(tài)規(guī)劃，甚至更簡(jiǎn)單寫，由于只是自身的記錄。而公共的則是兩個(gè)。原理都是動(dòng)態(tài)規(guī)劃的?！?】.最長(zhǎng)公共子序列問題和編輯距離問題。longest common subsequence。子序列是不要求連續(xù)相等的字符序列。這個(gè)問題也是算法導(dǎo)論上提過的問題。注意這個(gè)問題是Subsequence不是Substring。substring的話就是子串，子串的要求的連續(xù)相等的字符序列，而subsequence不要求連續(xù)。比如說

7、ABCD和ABD。他們的longest common subsequence就是ABD。而Longest common substring就是AB。這個(gè)問題和Edit Distance是同樣的一類問題。解決這類的問題都是從一個(gè)優(yōu)化的子結(jié)構(gòu)開始得到遞推式，從而給出一個(gè)一般的全局優(yōu)化結(jié)構(gòu)的過程。在這里，我們假定兩個(gè)字符串分別是S1和S2。他們的長(zhǎng)度是m和n。我們用Mi,j來表示一個(gè)長(zhǎng)度為i的S1和長(zhǎng)度為j的S2的最優(yōu)方案。我們要找的就是當(dāng)Mm,n是的方案。問題的關(guān)鍵就是要找到Mi,j和之前的那些諸如M1.i, 1.j之間的關(guān)系。/ m*n；我們把問題分成兩種情況來討論：1. 如果S1i = S2j

8、。就是i,j對(duì)應(yīng)位置上的字符相等。那么可以得出Mi,j = Mi-1,j-1+1;為什么呢？可以想象的。如果Mi-1,j-1也是一個(gè)最后方案，在這個(gè)最優(yōu)方案上我們同時(shí)增加一個(gè)字符。而這兩個(gè)字符又相等。那么我們只需要在這個(gè)Mi-1,j-1的最優(yōu)方案上+就可以了。2. 如果S1i != S2j。那么就拿Mi-1,j和Mi,j-1來比較。Mi,j的值就是Mi-1,j和Mi,j-1中大的值。這好比原來的字符串是S11.i-1是ABC，S21.j-1是ABE。那S11.i是ABCE，S21.j是ABEC?？梢钥闯鰜磉@個(gè)時(shí)候Mi,j不是由Mi-1,j-1決定的，而是由ABCE和ABE或者ABC和ABEC來

9、決定的，也就是Mi-1,j和Mi,j-1。所以我們可以把這個(gè)問題的遞歸式寫成：【4】.編輯距離。問題抽象歸類：（編輯距離問題）設(shè)A和B是2個(gè)字符串。要用最少的字符操作將字符串A轉(zhuǎn)換為字符串B。這里所說的字符操作包括:(1)刪除一個(gè)字符;(2)插入一個(gè)字符；(3)將一個(gè)字符改為另一個(gè)字符。 將字符串A變換為字符串B所用的最少字符操作數(shù)稱為字符串A到B的編輯距離,記為d(A,B)。試設(shè)計(jì)一個(gè)有效算法,對(duì)任給的2個(gè)字符串A和B,計(jì)算出它們的編輯距離d(A,B)。這個(gè)問題是動(dòng)態(tài)規(guī)劃中非?；A(chǔ)的一個(gè)問題，這個(gè)問題其實(shí)和另一個(gè)前面提到的問題很類似。就是Edit Distance的問題。編輯距離問題：Edi

10、t Distance問題又被成為L(zhǎng)evenshtein distance問題。這里的問題描述的就是兩個(gè)字符串經(jīng)過若干次修改（添加字符，刪除字符，替換字符）變?yōu)閮蓚€(gè)完全相等字符串。這里的distance就是指最少的修改次數(shù)。其實(shí)這個(gè)也就是編程之美中的那個(gè)字符串相似度的問題。相似的，我們還是定義一個(gè)Mi,j的二維模型。這時(shí)候一樣還是分析Mi,j的遞歸式。這里的結(jié)果還是比較相近的。如果S1i = S2j。那么Mi,j就等于Mi-1,j-1，就是說在S1i=S2j的情況下Mi,j不會(huì)發(fā)生變化，顯然不需要做什么改動(dòng)。edit(i, j) = edit(i-1, j-1);如果S1i != S2j的時(shí)候，

11、那么就是Mi-1,j-1,Mi-1,j和Mi,j-1來做比較，我們?nèi)∽钚〉哪莻€(gè)值+1就可以了。這里的Mi-1,j-1,Mi-1,j和Mi,j-1對(duì)應(yīng)了添加、刪除、替換這些操作。Mi-1,j-1可以替換最后一個(gè)S1i和Sj來完成，而Mi-1,j可以通過添加S1i來完成匹配。edit(i, j) = minedit(i-1, j)+1, edit(i, j-1)+1, edit(i-1, j-1)+1對(duì)應(yīng)添加，刪除和替換這三個(gè)操作?！?】.最長(zhǎng)遞增子序列（longest increase subsequence）既然已經(jīng)說到了最長(zhǎng)公共子序列，就把這個(gè)遞增子序列也說了。同樣的，這里subsequen

12、ce表明了這樣的子序列不要求是連續(xù)的。比如說有子序列1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 這樣一個(gè)字符串的的最長(zhǎng)遞增子序列就是1,3,4,5,6,7或者1,3,4,5,6,19。其實(shí)這個(gè)問題和前面的最長(zhǎng)公共子序列問題還是有一定的關(guān)聯(lián)的。假設(shè)我們的初始的序列S1。那我們從小到大先排序一下。得到了S1。這樣我們?cè)偾骃1和S1的最長(zhǎng)公共子序列就可以知道答案了：）是不是有點(diǎn)巧妙啊。這個(gè)過程還是比較直觀的。但是這個(gè)不是這次要說的重點(diǎn)，這個(gè)問題有比較傳統(tǒng)的做法的：我們定義L(j)是一個(gè)優(yōu)化的子結(jié)構(gòu),也就是最長(zhǎng)遞增子序列.那么L(j)和L(1.j-1)的關(guān)系可以描述

13、成：L(j) = max1; L(i)+1, (AiAj); 所有的ij;也就是說L(j)等于之前所有的L(i)中最大的的L(i)加一.這樣的L(i)需要滿足的條件就是AiAi,那么第i個(gè)元素可以直接接在L(i)子序列之后構(gòu)成一個(gè)更長(zhǎng)的子序列。與此同時(shí)，Aj本身也可以構(gòu)成一個(gè)長(zhǎng)度為1的，找個(gè)最大的?！?.1】. 問題1.造橋問題. 原題是這樣:Building Bridges。大致就是要在一條河的南北兩邊的各個(gè)城市之間造若干座橋橋兩邊的城市分別是a(1).a(n)和b(1).b(n).這里的要求a(i)只可以和b(i)之間造橋,同時(shí)兩座橋之間不能交叉.希望可以得到一個(gè)盡量多座橋的方案.都排序，

14、公共子序列問題。【5.2】. 這個(gè)問題的簡(jiǎn)要描述就是有若干個(gè)不同的箱子.你需要把他疊放的盡量的高.但是箱子的擺放必須滿足大的在下面,小的在上面的原則.箱子可以旋轉(zhuǎn)且數(shù)量不限.要求給出一組箱子就能求出能擺放的最大高度. 其實(shí)這個(gè)問題也是一個(gè)最長(zhǎng)遞增子序列的問題.只是隱藏的更深一點(diǎn). 因?yàn)橄渥涌梢苑D(zhuǎn)的緣故.我們首先定義我們的箱子的長(zhǎng)寬高分別是h,w,d.為了避免重復(fù)計(jì)算,我們約定w=d.這樣每個(gè)箱子可以改成3個(gè)箱子.這樣我們就不用在考慮旋轉(zhuǎn)的問題了.第一步,我們先把箱子按照w*d的值來排序.(為社么要排序讀者可以自己想想).然后我們的模型就開始用H(j)來表示第j個(gè)箱子時(shí)這個(gè)箱子的高度.記得最長(zhǎng)

15、遞增子序列的約束條件是AiAj.這里的條件只是改成了對(duì)應(yīng)的didj&wiwj.同時(shí)原來的+1也變成了+hi.hj = manhi, iwj & didj + hj;【6】動(dòng)態(tài)規(guī)劃算法求解硬幣找零問題 用一個(gè)實(shí)際例子來體現(xiàn)動(dòng)態(tài)規(guī)劃的算法思想硬幣找零問題。硬幣找零問題描述：現(xiàn)存在一堆面值為 V1、V2、V3 個(gè)單位的硬幣，問最少需要多少個(gè)硬幣才能找出總值為 T 個(gè)單位的零錢？假設(shè)這一堆面值分別為 1、2、5、21、25 元，需要找出總值 T 為 63 元的零錢。很明顯，只要拿出 3 個(gè) 21 元的硬幣就湊夠了 63 元了。但是，遞歸過程中，每次計(jì)算Count(i)，都會(huì)重復(fù)計(jì)算 Count(1).

16、Count(i-1); 這樣時(shí)間復(fù)雜度就是O(N2); 事實(shí)上，這是一個(gè)典型的動(dòng)態(tài)規(guī)劃問題，我們可以從1開始記錄下每個(gè)錢數(shù)所需的硬幣枚數(shù)，避免重復(fù)計(jì)算，為了能夠輸出硬幣序列，我們還需要記錄下每次新加入的硬幣?；谏鲜鰟?dòng)態(tài)規(guī)劃的思想，我們可以從 1 元開始計(jì)算出最少需要幾個(gè)硬幣，然后再求 2 元、3元每一次求得的結(jié)果都保存在一個(gè)數(shù)組中，以后需要用到時(shí)則直接取出即可。那么我們什么時(shí)候需要這些子問題的解呢？如何體現(xiàn)出由子問題的解得到較大問題的解呢？避免使用遞歸，那樣就將求得的結(jié)果保存在一個(gè)數(shù)組中，這樣從1-63，按照最小的尺度進(jìn)行計(jì)算保存每一個(gè)問題的最優(yōu)結(jié)果，和最優(yōu)解決方案。【7】. 這個(gè)問題又分成

17、01背包，完全背包，多重背包，分組背包等等。我在這里只記錄下01背包(0-1knapsack)和完全背包(unbounded knapsack)。背包問題的簡(jiǎn)單描述就是有一個(gè)背包和一堆物品。每個(gè)物品有自己的大小和價(jià)值。我們希望在一個(gè)特定容量的背包中放入價(jià)值盡可能大的物品。01背包呢就是每個(gè)物品最多只能放一次，也就是要么放要么不放，所以被稱為01背包。而完全背包呢就是每個(gè)物品可以放無限次。我們更喜歡unbounded knapsack這個(gè)名字。因?yàn)橥耆@次詞其實(shí)沒有表達(dá)清楚不限的意思。下面就是對(duì)完全背包和01背包就動(dòng)態(tài)規(guī)劃的方法做一些解析。這兩個(gè)問題中似乎01背包比較爽快，就從爽快的先說。類似的

18、，我們還是要找到一個(gè)優(yōu)化的子結(jié)構(gòu)，然后遞歸式，然后代碼。1.子問題；2.遞歸形式； 兩層循環(huán)，（i，j）?？梢赃x擇的余地，目標(biāo)，或者顛倒順序。我們用Mi,j來表示選用1.i件物品放入容量為j的背包時(shí)最大的價(jià)值。那樣就吧這個(gè)情況分成2中情況分析。很簡(jiǎn)單。用這第i個(gè)物品，或者不用。如果不用那么Mi,j就等于Mi-1,j（如果看不明白可以想象一下M的定義，這里Mi-1,j的意義就是用1.i-1個(gè)物品來裝容量為j的背包時(shí)的最優(yōu)策略，也就是不用第i個(gè)物品了。） 。那如果用呢？那就是Mi-1, j - si +vi。（因?yàn)榍懊娴牟呗砸呀?jīng)滿了j個(gè)容量，所以如果選用第i個(gè)物品，就要把總的容量j中減去第i個(gè)物品的容量，然后找到對(duì)應(yīng)的Mi-1, j - si加i的價(jià)值） 然后取一個(gè)大的值來決定選用那種策略。這個(gè)描述雖然有點(diǎn)拗口，但仔細(xì)琢磨意思還是直觀的。所以這個(gè)表達(dá)式