算法設(shè)計(jì)與分析 思政課件 第8、9章 動(dòng)態(tài)規(guī)劃、NP完全問題

第8章動(dòng)態(tài)規(guī)劃8.1動(dòng)態(tài)規(guī)劃概述8.2一維動(dòng)態(tài)規(guī)劃CONTENTS提綱8.3二維動(dòng)態(tài)規(guī)劃8.4三維動(dòng)態(tài)規(guī)劃8.5字符串動(dòng)態(tài)規(guī)劃8.6背包動(dòng)態(tài)規(guī)劃8.7樹形動(dòng)態(tài)規(guī)劃8.8區(qū)間動(dòng)態(tài)規(guī)劃1/878.1動(dòng)態(tài)規(guī)劃概述動(dòng)態(tài)規(guī)劃將要解決的問題轉(zhuǎn)化為一系列的子問題并且逐步加以解決，將前面解決子問題的結(jié)果作為后續(xù)解決子問題的條件，并且避免無意義的窮舉。2/87說明8.1.1從一個(gè)簡單示例入門【例8-1】一個(gè)樓梯有n（1≤n≤100）個(gè)臺(tái)階，上樓可以一步上1個(gè)臺(tái)階，也可以一步上2個(gè)臺(tái)階，設(shè)計(jì)一個(gè)算法求上樓梯共有多少種不同的走法。3/87解設(shè)f(n)表示上n個(gè)臺(tái)階的樓梯的走法數(shù)，顯然，f(1)=1，f(2)=2（一種走法是一步上1個(gè)臺(tái)階、走2步，另外一種走法是一步上2個(gè)臺(tái)階）。對(duì)于大于2的n個(gè)臺(tái)階的樓梯：一種走法是第一步上1個(gè)臺(tái)階，剩余n-1個(gè)臺(tái)階的走法數(shù)是f(n-1)；另外一種走法是第一步上2個(gè)臺(tái)階，剩余n-2個(gè)臺(tái)階的走法數(shù)是f(n-2)。所以有f(n)=f(n-2)+f(n-1)。對(duì)應(yīng)的遞歸模型如下：f(1)=1f(2)=2f(n)=f(n-2)+f(n-1) n>24/87intf1(intn) //算法1{ if(n==1)return1; elseif(n==2)return2; elsereturnf1(n-2)+f1(n-1);}f1(5)f1(3)f1(4)f1(1)f1(2)f1(3)f1(1)f1(2)f1(2)存在大量重復(fù)的子問題5/87intdp[MAXN];intf21(intn) //被f2函數(shù)調(diào)用{ if(dp[n]!=0)returndp[n]; if(n==1)dp[n]=1; elseif(n==2)dp[n]=2; elsedp[i]=f21(i-2)+f21(i-1); returndp[n];}intf2(intn) //算法2{ memset(dp,0,sizeof(dp)); returnf21(n);}如何避免重疊子問題的重復(fù)計(jì)算呢？可以設(shè)計(jì)一個(gè)一維dp數(shù)組，用dp[i]存放f1(i)的值。6/87上述算法2采用遞歸算法，可以直接采用迭代實(shí)現(xiàn)，仍然設(shè)計(jì)一維dp數(shù)組，用dp[i]存放f1(i)的值。intf3(intn) //算法3{ intdp[MAXN]; dp[1]=1; dp[2]=2; for(inti=3;i<=n;i++) dp[i]=dp[i-2]+dp[i-1]; returndp[n];}7/87上述算法3就是動(dòng)態(tài)規(guī)劃算法，其中數(shù)組dp（表）稱為動(dòng)態(tài)規(guī)劃數(shù)組，從中看出動(dòng)態(tài)規(guī)劃就是記錄子問題的結(jié)果再利用的方法。原問題子問題1子問題2子問題k…表原問題的解8/87f(1)f(n-2)f(n-1)f(n)…f(n)=f(n-2)+f(n-1)intf4(intn) //算法4{ intdp[3];

dp[0]=1;dp[1]=2; for(inti=2;i<n;i++)

dp[i%3]=dp[(i-1)%3]+dp[(i-2)%3]; returndp[(n-1)%3];}9/87最常見的算法intf5(intn) //算法5{ if(n==1)return1; elseif(n==2)return2; else { inta=1,b=2,c; for(inti=3;i<=n;i++) { c=a+b; a=b;b=c; } returnc; }}10/878.1.2動(dòng)態(tài)規(guī)劃的原理一個(gè)多段圖G=（V，E），在頂點(diǎn)0處有一水庫，現(xiàn)需要從頂點(diǎn)0鋪設(shè)一條管道到頂點(diǎn)9，邊上的數(shù)字表示對(duì)應(yīng)兩個(gè)頂點(diǎn)之間的距離，該圖采用鄰接矩陣A表示?，F(xiàn)要找出一條從頂點(diǎn)0到頂點(diǎn)9的線路，使得鋪設(shè)的管道長度最短。5343343633474236242012345678911/8753433436334742362420123456789階段0階段1階段2階段3階段4S0={0}S1={1,2,3}S2={4,5,6}S4={9}S3={7,8}分為5個(gè)階段，通常階段變量用k表示，這里k為0～4。階段k可能有多個(gè)狀態(tài)，通常用狀態(tài)集合Sk表示，例如S1={1，2，3}。狀態(tài)變量xk表示Sk中某個(gè)狀態(tài)，如x1可以取S1中的任意值。12/87動(dòng)態(tài)規(guī)劃中當(dāng)前階段的狀態(tài)往往是上一階段狀態(tài)和相應(yīng)決策的結(jié)果，采用指標(biāo)函數(shù)表示它們之間關(guān)系稱為狀態(tài)轉(zhuǎn)移方程，指標(biāo)函數(shù)通常是最優(yōu)解函數(shù)。設(shè)最優(yōu)解函數(shù)f(s)為狀態(tài)s到終點(diǎn)9的最短路徑長度，用k表示階段。狀態(tài)轉(zhuǎn)移方程：53433436334742362420123456789階段0階段1階段2階段3階段4S0={0}S1={1,2,3}S2={4,5,6}S4={9}S3={7,8}f4(9)=0fk(s)=min<s,t>∈E{A[s][t]+fk+1(t)} k從3到013/87從k=3開始直到k=0為止，f0(0)就是最短管道長度，稱為逆序解法。設(shè)計(jì)二維動(dòng)態(tài)規(guī)劃數(shù)組dp[K][MAXN]，dp[k][s]表示fk(s)的結(jié)果，起始點(diǎn)start=0，終點(diǎn)end=9。05343343633474236242012345678934676119912f4(9)=0fk(s)=min<s,t>∈E{A[s][t]+fk+1(t)} k從3到014/87也可以設(shè)最優(yōu)解函數(shù)f(s)為起點(diǎn)0到狀態(tài)s的最短路徑長度狀態(tài)轉(zhuǎn)移方程：f0(0)=0fk(t)=min<s,t>∈E{fk-1(s)+A[s][t]} k從1到415/8753433436334742362420123456789108758243012這樣求解過程是從k=1開始直到k=4為止，f4(9)就是最短管道長度，稱為順序解法。f0(0)=0fk(t)=min<s,t>∈E{fk-1(s)+A[s][t]} k從1到416/878.1.3動(dòng)態(tài)規(guī)劃求解問題的性質(zhì)和步驟最優(yōu)子結(jié)構(gòu)：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，即滿足最優(yōu)性原理。無后效性：如果某個(gè)階段狀態(tài)一旦確定，就不受以后決策的影響，也就是說某個(gè)狀態(tài)以后的決策不會(huì)影響以前的狀態(tài)。重疊子問題：一個(gè)問題分解的若干子問題之間是不獨(dú)立的，其中一些子問題在后面的決策中可能被多次重復(fù)使用。該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)。采用動(dòng)態(tài)規(guī)劃求解的問題一般要具有以下3個(gè)性質(zhì)17/87確定狀態(tài)：將問題求解中各個(gè)階段所處的各種情況用不同的狀態(tài)表示出來。確定狀態(tài)轉(zhuǎn)移方程：描述求解中各個(gè)階段的狀態(tài)轉(zhuǎn)移和指標(biāo)函數(shù)的關(guān)系。確定初始條件和邊界情況：狀態(tài)轉(zhuǎn)移方程通常是一個(gè)遞推式，初始條件通常指定遞推的起點(diǎn)，在遞推中需要考慮一些特殊情況，稱為邊界情況。確定計(jì)算順序：也就是指定求狀態(tài)轉(zhuǎn)移方程的順序，是順序求解還是逆序求解。消除冗余：如采用滾動(dòng)數(shù)組進(jìn)一步提高時(shí)空性能。一般來說動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)要經(jīng)歷以下幾個(gè)步驟18/878.1.4動(dòng)態(tài)規(guī)劃與其他方法的比較動(dòng)態(tài)規(guī)劃的基本思想與分治法類似，也是將求解的問題分解為若干個(gè)子問題（階段），按照一定的順序求解子問題，前一個(gè)子問題的解有助于后一個(gè)子問題的求解。但分治法中各個(gè)子問題是獨(dú)立的（不重疊），而動(dòng)態(tài)規(guī)劃適用于子問題重疊的情況。動(dòng)態(tài)規(guī)劃又和貪心法有些相似，都需要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，都是將一個(gè)問題的解決方案視為一系列決策的結(jié)果。不同的是貪心法每次采用貪心選擇便做出一個(gè)不可回溯的決策，而動(dòng)態(tài)規(guī)劃算法中隱含有回溯的過程。19/878.2一維動(dòng)態(tài)規(guī)劃一維動(dòng)態(tài)規(guī)劃是指設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法中采用一維動(dòng)態(tài)規(guī)劃數(shù)組，也稱為線性動(dòng)態(tài)規(guī)劃。20/87說明8.2.1最大連續(xù)子序列和給定一個(gè)含n（n≥1）個(gè)整數(shù)的序列，要求求出其中最大連續(xù)子序列的和。序列（-2，11，-4，13，-5，-2）的最大子序列和為20。序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子序列和為16。規(guī)定一個(gè)序列最大連續(xù)子序列和至少是0，如果小于0，其結(jié)果為0。21/87解dp[0]=a[0] 初始條件dp[i]=max(dp[i-1]+ai，ai) i>022/87

設(shè)計(jì)一維動(dòng)態(tài)規(guī)劃dp，dp[i]（1≤i≤n-1）表示以元素ai結(jié)尾的最大連續(xù)子序列和，顯然dp[i-1]表示以元素ai-1結(jié)尾的最大連續(xù)子序列和。判斷ai分為兩種情況：①將ai合并到前面以元素ai-1結(jié)尾的最大連續(xù)子序列中，此時(shí)有

dp[i]=dp[i-1]+ai。②不將ai合并到前面以元素ai-1結(jié)尾的最大連續(xù)子序列中，即從

ai開始構(gòu)造一個(gè)連續(xù)子序列，此時(shí)有dp[i]=ai。ans=dp[3]=20dp[0]=-20-2dp[1]=11111dp[2]=72-4dp[3]=20313dp[4]=154-5dp[5]=135-2max求出dp中的最大元素ans。由于本題中最大連續(xù)子序列和至少為0（或者說最大連續(xù)子序列可以為空序列），所以最后的最大連續(xù)子序列和應(yīng)該為max(ans，0)。23/87intdp[MAXN];intmaxSubSum(vector<int>&a) //求最大連續(xù)子序列和{ intn=a.size(); memset(dp,0,sizeof(dp));

dp[0]=a[0]; for(inti=1;i<n;i++) //計(jì)算順序是j從1到n-1

dp[i]=max(dp[i-1]+a[i],a[i]); intans=dp[0]; for(inti=1;i<n;i++) ans=max(ans,dp[i]); returnmax(ans,0);}【算法分析】maxSubSum算法含兩個(gè)for循環(huán)（實(shí)際上第二個(gè)for循環(huán)可以合并到第一個(gè)for循環(huán)中），對(duì)應(yīng)時(shí)間復(fù)雜度均為O(n)。算法中應(yīng)用了dp數(shù)組，對(duì)應(yīng)的空間復(fù)雜度為O(n)。24/87當(dāng)求出dp后可以推導(dǎo)出一個(gè)最大連續(xù)子序列（實(shí)際上這樣的最大連續(xù)子序列可能有多個(gè)，這里僅僅求出其中的一個(gè)）。先在dp數(shù)組中求出最大元素的序號(hào)maxi，i從maxi序號(hào)開始在a中向前查找，rsum從dp[maxi]開始遞減a[i]，直到rsum為0，對(duì)應(yīng)的a中子序列就是一個(gè)最大連續(xù)子序列。i=maxi=3rsum=7dp[0]=-20-2dp[1]=11111dp[2]=72-4dp[3]=20313dp[4]=154-5dp[5]=135-2逆置maxi=2rsum=11i=1rsum=0{11，-4，13}25/8726/87vector<int>maxSub(vector<int>&a) //求一個(gè)最大連續(xù)子序列{ intn=a.size(); vector<int>x; intmaxi=0; for(inti=1;i<n;i++) //求dp中最大元素序號(hào)maxi if(dp[i]>dp[maxi]) maxi=i; intrsum=dp[maxi]; inti=maxi; while(i>=0&&rsum!=0) { rsum-=a[i]; x.push_back(a[i]); i--; }

reverse(x.begin(),x.end()); returnx;}空間優(yōu)化如果只需要求最大連續(xù)子序列和，可以采用滾動(dòng)數(shù)組優(yōu)化空間。maxSubSum算法中用j標(biāo)識(shí)階段，由于dp[j]僅僅與dp[j-1]相關(guān)，將一維dp數(shù)組改為單個(gè)變量dp。intmaxSubSum1(vector<int>&nums) //求最大連續(xù)子序列和{ intn=nums.size(); intdp;

dp=nums[0]; intans=dp; for(inti=1;i<n;i++) //計(jì)算順序是i從1到n-1循環(huán) { dp=max(dp+nums[i],nums[i]); ans=max(ans,dp); } returnmax(ans,0);}空間復(fù)雜度為O(1)27/878.2.2實(shí)戰(zhàn)—最大子序和（LeetCode53）問題描述:給定一個(gè)含n（1≤n≤30000）個(gè)整數(shù)的數(shù)組

nums（整數(shù)值在-100000到100000之間），找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

例如nums={-2,-1}，結(jié)果為-1。

要求設(shè)計(jì)如下函數(shù)：classSolution{public:intmaxSubArray(vector<int>&nums){}};28/87解本題采用動(dòng)態(tài)規(guī)劃求解的原理見8.2.1節(jié)，這里僅僅需要求最大連續(xù)子序列和，而且該最大連續(xù)子序列至少含一個(gè)元素。采用滾動(dòng)數(shù)組。29/87classSolution{public: intmaxSubArray(vector<int>&nums) { intn=nums.size(); if(n==1)returnnums[0]; intdp; dp=nums[0]; intans=dp; for(intj=1;j<n;j++) { dp=max(dp+nums[j],nums[j]);

ans=max(ans,dp); } returnans; //不能改為max(ans,0) }};30/878.2.3最長遞增子序列問題描述：給定一個(gè)無序的整數(shù)序列a[0..n-1]，求其中最長遞增（嚴(yán)格）子序列的長度。例如，a={2，1，5，3，6，4，8，9，7}，n=9，其最長遞增子序列為{1，3，4，8，9}，結(jié)果為5。31/87解dp[i]表示以a[i]結(jié)尾的子序列a[0..i]（共i+1個(gè)元素）中的最長遞增子序列的長度。計(jì)算順序是i從0到n-1，對(duì)于每個(gè)a[i]，dp[i]置為1（表示只有a[i]一個(gè)元素時(shí)最長遞增子序列的長度為1）。32/87考慮a[0..i-1]中的每一個(gè)元素a[j]，分為兩種情況：若a[j]<a[i]，則以aj結(jié)尾的最長遞增子序列加上ai可能構(gòu)成一個(gè)更長的遞增子序列，此時(shí)有dp[i]=max(dp[i]，dp[j]+1)。a0

a1

aj

…

ai-1

ai

…

an-1dp[j]dp[i]=max(dp[i],dp[j]+1)aj<ai否則最長遞增子序列沒有改變。在求出dp數(shù)組后，通過順序遍歷dp求出最大值ans，則ans就是最長遞增（嚴(yán)格）子序列的長度。33/87狀態(tài)轉(zhuǎn)移方程dp[i]=1 0≤i≤n-1（初始條件）dp[i]=maxa[j]<a[i](j<i){dp[j]+1} 0≤i≤n-134/87intmaxInclen(vector<int>&a) //求最長遞增子序列長度{ intn=a.size(); for(inti=0;i<n;i++) { dp[i]=1; for(intj=0;j<i;j++) { if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1); } } intans=dp[0]; for(inti=1;i<n;i++) ans=max(ans,dp[i]); returnans;}【算法分析】時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(n)。35/87當(dāng)求出dp后可以推導(dǎo)出一個(gè)最長遞增子序列。先在dp數(shù)組中求出最大元素的序號(hào)maxj，置j=maxj，prej從j的前一個(gè)序號(hào)開始在a中向前查找，rnum從dp[maxj]開始，若a[prej]<a[j]置rnum--，直到rnum為0，對(duì)應(yīng)的a中子序列就是一個(gè)最大連續(xù)子序列。a0

a1

aj

…

ai-1

ai

…

an-1maxjdp[i]=max(dp[i],dp[[j]+1)aj<ai36/87vector<int>maxInc(vector<int>&a) //求一個(gè)最長遞增子序列{ intn=a.size(); vector<int>x; intmaxj=0; for(intj=1;j<n;j++) if(dp[j]>dp[maxj])maxj=j;

x.push_back(a[maxj]); intrnum=dp[maxj]-1; //剩余的元素個(gè)數(shù) intj=maxj; //j指向當(dāng)前最長遞增子序列的一個(gè)元素 intprej=maxj-1; //prej查找最長遞增子序列的前一個(gè)元素 while(prej>=0&&rnum!=0) { if(a[prej]<a[j]) { rnum--;

x.push_back(a[prej]); j=prej;prej--; } elseprej--; } reverse(x.begin(),x.end()); returnx;}37/878.2.4*活動(dòng)安排問題Ⅱ假設(shè)有n個(gè)活動(dòng)和一個(gè)資源，每個(gè)活動(dòng)執(zhí)行時(shí)都要占用該資源，并且該資源任何時(shí)刻只能被一個(gè)活動(dòng)所占用，一旦某個(gè)活動(dòng)開始執(zhí)行，中間不能被打斷，直到其執(zhí)行完畢。每個(gè)活動(dòng)i有一個(gè)開始時(shí)間bi和結(jié)束時(shí)間ei（bi<ei），它是一個(gè)半開時(shí)間區(qū)間[bi，ei），其占用資源的時(shí)間=ei-bi。假設(shè)最早活動(dòng)執(zhí)行時(shí)間為0。求一種最優(yōu)活動(dòng)安排方案，使得安排的活動(dòng)的總占用時(shí)間最長。38/8711個(gè)活動(dòng)（已按結(jié)束時(shí)間的遞增排列）活動(dòng)i012345678910開始時(shí)間130535688212結(jié)束時(shí)間456789101112131539/87解該問題與7.2.1節(jié)的活動(dòng)安排問題Ⅰ類似，不同的是這里求一個(gè)總占用時(shí)間最長的兼容活動(dòng)子集，而不是求活動(dòng)個(gè)數(shù)最多的兼容活動(dòng)子集，兩者是不同的。這里采用貪心法+動(dòng)態(tài)規(guī)劃的思路，先求出每個(gè)活動(dòng)A[i]的占用資源的時(shí)間A[i].length=A[i].e-A[i].b，將活動(dòng)數(shù)組A[0..n-1]按結(jié)束時(shí)間遞增排序（貪心思路）。40/87設(shè)計(jì)一維動(dòng)態(tài)規(guī)劃數(shù)組dp，dp[i]表示A[0..i]（共i+1個(gè)活動(dòng)）中所有兼容活動(dòng)的最長占用時(shí)間。考慮活動(dòng)i，找到前面與之兼容的最晚的活動(dòng)j，即，稱活動(dòng)j為活動(dòng)i的前驅(qū)活動(dòng)，如果活動(dòng)i找到了前驅(qū)活動(dòng)j，可以有兩種選擇：①活動(dòng)j之后不選擇活動(dòng)i，此時(shí)dp[i]=dp[i-1]。②活動(dòng)j之后選擇活動(dòng)i，此時(shí)dp[i]=dp[j]+A[i].length。兩種情況中取最大值。對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移方程如下：dp[0]=活動(dòng)0的時(shí)間

邊界情況dp[i]=max{dp[i-1]，dp[j]+A[i].length} 活動(dòng)j是活動(dòng)i的前驅(qū)活動(dòng)41/87

求出dp數(shù)組后，dp[n-1]就是最長的總占用時(shí)間。為了求一個(gè)最優(yōu)安排方案，設(shè)計(jì)一個(gè)一維數(shù)組pre，pre[i]的含義如下：①若活動(dòng)i沒有前驅(qū)活動(dòng)，置pre[i]=-2。②若活動(dòng)i有前驅(qū)活動(dòng)j，但不選擇活動(dòng)i，置pre[i]=-1。③若活動(dòng)i有前驅(qū)活動(dòng)j，選擇活動(dòng)i，置pre[i]=j。42/8711個(gè)活動(dòng)求出的dp和pre如下所示。dp[10]=13活動(dòng)i012345678910開始時(shí)間130535688212結(jié)束時(shí)間4567891011121315length326254434113dp[i]3266561010101113pre[i]-2-2-2-1-212-1-1-2843/87structAction

//活動(dòng)的類型{ intb,e; //開始時(shí)間和結(jié)束時(shí)間 intlength; //活動(dòng)的占用時(shí)間 booloperator<(constActiont)const { returne<t.e; //按結(jié)束時(shí)間遞增排序 }};intn=11; //活動(dòng)個(gè)數(shù)ActionA[MAXN]={{1,4},{3,5},{0,6},{5,7},{3,8},{5,9},{6,10},{8,11},{8,12},{2,13},{12,15}};intdp[MAXN]; //一維動(dòng)態(tài)規(guī)劃數(shù)組intpre[MAXN]; //pre[i]存放前驅(qū)活動(dòng)序號(hào)44/87intplan() //求解算法{ memset(dp,0,sizeof(dp)); //dp數(shù)組初始化

sort(A,A+n);

//排序

dp[0]=A[0].length;

pre[0]=-2;

//活動(dòng)0沒有前驅(qū)活動(dòng) for(inti=1;i<n;i++) { intj=i-1; while(j>=0&&A[j].e>A[i].b) j--; //在A[0..i-1]找與活動(dòng)i兼容的最晚活動(dòng)j if(j==-1) //活動(dòng)i前面沒有兼容活動(dòng) { dp[i]=A[i].length;

pre[i]=-2;

//表示沒有前驅(qū)活動(dòng) }45/87 else //活動(dòng)i前面有最晚兼容活動(dòng)j { if(dp[i-1]>=dp[j]+A[i].length) //dp[i]=max(dp[i-1],dp[j]+A[i].length) { dp[i]=dp[i-1];

pre[i]=-1;

//不選擇活動(dòng)i } else { dp[i]=dp[j]+A[i].length;

pre[i]=j;

//選中活動(dòng)i,前驅(qū)活動(dòng)為活動(dòng)j } } } returndp[n-1]; //返回最優(yōu)解}【算法分析】主要時(shí)間花費(fèi)在排序上，對(duì)應(yīng)的時(shí)間復(fù)雜度為O(nlog2n)。46/87求一個(gè)最優(yōu)安排方案x活動(dòng)i012345678910dp[i]3266561010101113pre[i]-2-2-2-1-212-1-1-28i=n-1=10pre[10]=8活動(dòng)10√

xi=pre[10]=8pre[8]=-1活動(dòng)8×i減1

i=7pre[6]=2活動(dòng)6√

xi=pre[6]=2pre[2]=-2活動(dòng)2√

xi=pre[2]=-2i=-2說明沒有前驅(qū)活動(dòng)，結(jié)束pre[7]=-1活動(dòng)7×

i減1

i=647/87voidgetx() //求一個(gè)最優(yōu)安排方案{ vector<int>x; //存放一個(gè)方案 inti=n-1; //從n-1開始 while(true) { if(i==-2) //活動(dòng)i沒有前驅(qū)活動(dòng) break; if(pre[i]==-1) //不選擇活動(dòng)i i--; else //選擇活動(dòng)i { x.push_back(i); i=pre[i]; } } printf("選擇的活動(dòng):"); //輸出結(jié)果 for(inti=x.size()-1;i>=0;i--) printf("%d[%d,%d]",x[i],A[x[i]].b,A[x[i]].e); printf("\n"); printf("最長占用時(shí)間:%d\n",dp[n-1]);}48/878.3二維動(dòng)態(tài)規(guī)劃二維動(dòng)態(tài)規(guī)劃是指設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法中采用二維動(dòng)態(tài)規(guī)劃數(shù)組，也稱為坐標(biāo)型動(dòng)態(tài)規(guī)劃。49/87說明8.3.1三角形最小路徑和給定一個(gè)高度為n的整數(shù)三角形，求從頂部到底部的最小路徑和及其一條最小路徑，從每個(gè)整數(shù)出發(fā)只能向下移動(dòng)到相鄰的整數(shù)。例如，一個(gè)n=4的三角形，輸出的最小路徑和是13，一條最小路徑是2，3，5，3。234726598350/87解問題求解—自頂向下2347265983i-1，ji-1，j-1i，jJI234726598351/87

設(shè)計(jì)二維動(dòng)態(tài)規(guī)劃數(shù)組dp，dp[i][j]表示從頂部a[0][0]到達(dá)（i，j）位置的最小路徑和。起始位置只有（0，0），所以初始化為dp[0][0]=a[0][0]。這里有如下兩個(gè)邊界：對(duì)于j=0即第0列的任意位置（i，0），只有垂直方向到達(dá)的一條路徑，此時(shí)有dp[i][0]=dp[i-1][0]+a[i][0]。對(duì)于i=j即對(duì)角線上的任意位置（i，i），只有左斜方向到達(dá)的一條路徑，此時(shí)有dp[i][i]=dp[i-1][i-1]+a[i][i]。

其他兩條到達(dá)（i，j）位置的路徑，最小路徑和dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+a[i][j]。i-1,ji-1,j-1i，jJI52/87dp[0][0]=a[0][0] 初始條件dp[i][0]=dp[i-1][0]+a[i][0] 第0列的邊界情況，1≤i≤n-1dp[i][i]=dp[i-1][i-1]+a[i][i] 對(duì)角線的邊界情況，1≤i≤n-1dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+a[i][j] i>1的其他有兩條達(dá)到路徑在dp數(shù)組的第n-1行中求出的最小元素ans=dp[n-1][minj]。53/87intminPathSum(vector<vector<int>>&a) //自頂向下求最小路徑和{ intn=a.size(); dp[0][0]=a[0][0]; for(inti=1;i<n;i++) //考慮第0列的邊界

dp[i][0]=dp[i-1][0]+a[i][0]; for(inti=1;i<n;i++) //考慮對(duì)角線的邊界

dp[i][i]=a[i][i]+dp[i-1][i-1]; for(inti=2;i<n;i++) //考慮其他有兩條達(dá)到的路徑 { for(intj=1;j<i;j++)

dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+a[i][j]; } intans=dp[n-1][0]; for(intj=1;j<n;j++) //求出最小ans ans=min(ans,dp[n-1][j]); returnans;}54/87那么如何找到一條最小和的路徑呢？設(shè)計(jì)一個(gè)二維數(shù)組pre，pre[i][j]表示到達(dá)（i，j）位置時(shí)最小路徑上的前驅(qū)位置，由于前驅(qū)位置只有兩個(gè)即（i-1，j-1）和（i-1，j），用pre[i][j]記錄前驅(qū)位置的列號(hào)即可。i-1，ji-1，j-1i，jpre[i][j]=j-1i-1，ji-1，j-1i，jpre[i][j]=j55/87在求出ans后，通過pre[n-1][minj]推導(dǎo)求出反向路徑path，逆向輸出得到一條最小和的路徑。voidminPathSum1(vector<vector<int>>&a) //求最小路徑和以及一條最小和路徑{ intpre[MAXN][MAXN]; //路徑數(shù)組 intn=a.size(); dp[0][0]=a[0][0]; for(inti=1;i<n;i++) //考慮第0列的邊界 { dp[i][0]=dp[i-1][0]+a[i][0];

pre[i][0]=0; } for(inti=1;i<n;i++) //考慮對(duì)角線的邊界 { dp[i][i]=a[i][i]+dp[i-1][i-1];

pre[i][i]=i-1; }56/87i-1，0i，0pre[i][j]=0i-1，i-1i，ipre[i][i]=i-1 for(inti=2;i<n;i++) //考慮其他有兩條達(dá)到路徑的結(jié)點(diǎn) { for(intj=1;j<i;j++) { if(dp[i-1][j-1]<dp[i-1][j]) { pre[i][j]=j-1;

dp[i][j]=a[i][j]+dp[i-1][j-1]; } else { pre[i][j]=j;

dp[i][j]=a[i][j]+dp[i-1][j]; } } }57/87i-1，ji-1，j-1i，jpre[i][j]=j-1i-1，ji-1，j-1i，jpre[i][j]=j intans=dp[n-1][0]; intminj=0; for(intj=1;j<n;j++) //求出最小ans和對(duì)應(yīng)的列號(hào)minj { if(ans>dp[n-1][j]) { ans=dp[n-1][j];

minj=j; } } printf("最小路徑和ans=%d\n",ans); inti=n-1; vector<int>path; //存放一條路徑 while(i>=0) //從(n-1,minj)位置推導(dǎo)反向路徑 { path.push_back(a[i][minj]);

minj=pre[i][minj];

//最小路徑在前一行中的列號(hào) i--; //在前一行查找 } printf("最小路徑:"); for(inti=path.size()-1;i>=0;i--) //反向輸出path printf("%d",path[i]); printf("\n");}58/87問題求解—自底向上i+1，j+1i+1，ji，

jJI234726598359/87

設(shè)計(jì)二維動(dòng)態(tài)規(guī)劃數(shù)組dp，其中dp[i][j]表示從底部到達(dá)（i，j）位置的最小路徑和。起始位置只有（n-1，*），所以初始化為dp[n-1][j]=a[n-1][j]。同樣有如下兩個(gè)邊界：對(duì)于j=0即第0列的任意位置（i，0），只有垂直方向到達(dá)的一條路徑，此時(shí)有dp[i][0]=dp[i+1][0]+a[i][0]。對(duì)于i=j即對(duì)角線上的任意位置（i，i），只有左斜方向到達(dá)的一條路徑，此時(shí)有dp[i][i]=dp[i+1][i+1]+a[i][i]。

其他兩條到達(dá)（i，j）位置的路徑，最小路徑和dp[i][j]=min(dp[i+1][j+1]，dp[i+1][j])+a[i][j]。i+1，j+1i+1，ji,，jJI60/87dp[n-1][j]=a[n-1][j] 初始條件dp[i][0]=dp[i+1][0]+a[i][0] 第0列的邊界情況，0≤i≤n-2dp[i][i]=dp[i+1][i+1]+a[i][i] 對(duì)角線的邊界情況，0≤i≤n-2dp[i][j]=min(dp[i+1][j]，dp[i+1][j+1])+a[i][j] i<n-1的其他有兩條達(dá)到路徑由于第0行只有一個(gè)元素，所以dp[0][0]就是最終的最小路徑和。61/87intminPathSum2(vector<vector<int>>&a) //自底向上求最小路徑和{ intn=a.size(); intdp[MAXN][MAXN]; for(intj=0;j<n;j++)

dp[n-1][j]=a[n-1][j];

//第n-1行初始化 for(inti=n-2;i>=0;i--) //考慮第0列的邊界

dp[i][0]=dp[i+1][0]+a[i][0]; for(inti=n-2;i>=0;i--) //考慮對(duì)角線的邊界

dp[i][i]=a[i][i]+dp[i+1][i+1]; for(inti=n-2;i>=0;i--) //考慮其他有兩條達(dá)到的路徑 { for(intj=0;j<a[i].size();j++)

dp[i][j]=min(dp[i+1][j+1],dp[i+1][j])+a[i][j]; } returndp[0][0];}62/87自底向上算法空間優(yōu)化在自底向上算法中階段i（指求第i行的dp）僅僅與階段i+1相關(guān)，采用降維滾動(dòng)數(shù)組方式，將dp由二維數(shù)組改為一維數(shù)組。intminPathSum3(vector<vector<int>>&a) //自底向上的優(yōu)化算法{ intn=a.size(); intdp[MAXN]; //一維動(dòng)態(tài)規(guī)劃數(shù)組

memset(dp,0,sizeof(dp)); for(inti=n-1;i>=0;i--) { for(intj=0;j<a[i].size();j++) //含邊界情況的處理

dp[j]=min(dp[j],dp[j+1])+a[i][j]; } returndp[0];}63/878.3.2實(shí)戰(zhàn)—下降路徑最小和（LeetCode931）問題描述：給定一個(gè)n×n（1≤n≤100）的整數(shù)數(shù)組

matrix（元素值位于-100～100），找出并返回通過

matrix

的下降路徑的最小和。下降路徑可以從第一行中的任何元素開始，并從每一行中選擇一個(gè)元素。在下一行選擇的元素和當(dāng)前行所選元素最多相隔一列（即位于正下方或者沿對(duì)角線向左或者向右的第一個(gè)元素）。具體來說，位置（i，j）的下一個(gè)元素應(yīng)當(dāng)是（i+1，j-1）、（i+1，j）或者（i+1，j+1）。

例如，matrix={{2，1，3}，{6，5，4}，{7，8，9}}，答案是13。231645798(a)路徑1231645798(b)路徑264/87解問題求解—自上而下dp[i][j]表示從第0行開始并且以（i，j）位置為終點(diǎn)的下降路徑中最小路徑和。采用自上而下的方式求dp。到達(dá)（i，j）位置的路徑有3條。i-1，ji，ji-1，j-1i-1，j+1min65/87第0行：dp[0][j]=matrix[0][j]。一般情況：

dp[i][j]=min3(dp[i-1][j-1]，dp[i-1][j]，dp[i-1][j+1])+matrix[i][j]。考慮邊界情況如下：①當(dāng)j=0時(shí)有dp[i][j]=min(dp[i-1][j]，dp[i-1][j+1])+matrix[i][j]。②當(dāng)j=n-1時(shí)有dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+matrix[i][j]。上述各式合起來構(gòu)成狀態(tài)轉(zhuǎn)移方程，由其求出dp數(shù)組，那么dp中第n-1行的最小值就是第0行開始到第n-1行的下降路徑中最小路徑和。i-1，ji，ji-1，j-1i-1，j+1min66/87class

Solution

{public: int

minFallingPathSum(vector<vector<int>>&

matrix)

{ int

n=matrix.size();

int

ans;

if(n==1)

//n=1為特殊情況，返回第0行的最小元素

{ ans=matrix[0][0];

for(int

j=1;j<n;j++)

if

(matrix[0][j]<ans)

ans=matrix[0][j];

return

ans;

}67/87

intdp[n][n]; memset(dp,0,sizeof(dp));

for(int

j=0;j<n;j++)

//第0行:邊界情況

dp[0][j]=matrix[0][j];

for(int

i=1;i<n;i++)

{ for(int

j=0;j<n;j++)

{ if(j==0)

dp[i][j]=min(dp[i-1][j],dp[i-1][j+1])+matrix[i][j];

else

if(j==n-1)

dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+matrix[i][j];

else

dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))+matrix[i][j];

}

}

ans=dp[n-1][0];

//求dp第n-1行中的最小元素ans

for(int

j=1;j<n;j++)

if(dp[n-1][j]<ans)

ans=dp[n-1][j];

return

ans;

}};68/87自上而下算法空間優(yōu)化由于dp[i]僅僅與dp[i-1]相關(guān)，采用滾動(dòng)數(shù)組方法，將dp數(shù)組大小改為dp[2][n]，用dp[0][j]存放dp[i-1][j]，用dp[1][j]存放dp[i][j]。class

Solution

{public: int

minFallingPathSum(vector<vector<int>>&

matrix)

{ int

n=matrix.size();

int

ans;

if(n==1)

//n=1為特殊情況，返回第0行的最小元素

{ ans=matrix[0][0];

for(int

j=1;j<n;j++)

if

(matrix[0][j]<ans)

ans=matrix[0][j];

return

ans;

}

int

dp[2][n];

memset(dp,0,sizeof(dp));69/87

for(int

j=0;j<n;j++)

//第0行:邊界情況

dp[0][j]=matrix[0][j];

int

c=0;

for(int

i=1;i<n;i++)

{ c=1-c;

for(int

j=0;j<n;j++)

{ if(j==0)

dp[c][j]=min(dp[1-c][j],dp[1-c][j+1])+matrix[i][j];

else

if(j==n-1)

dp[c][j]=min(dp[1-c][j-1],dp[1-c][j])+matrix[i][j];

else

dp[c][j]=min(dp[1-c][j-1],min(dp[1-c][j],dp[1-c][j+1]))+matrix[i][j];

}

}

ans=dp[c][0];

//求dp第n-1行中的最小元素ans

for(int

j=1;j<n;j++)

if(dp[c][j]<ans)

ans=dp[c][j];

return

ans;

}};70/87也可以：1-cc&0c&1自下而上算法空間優(yōu)化問題求解—自下而上71/87自學(xué)(老師講的太多了)8.4三維動(dòng)態(tài)規(guī)劃三維動(dòng)態(tài)規(guī)劃是指設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法中采用三維動(dòng)態(tài)規(guī)劃數(shù)組。72/87說明8.4.1Floyd算法設(shè)計(jì)二維數(shù)組B存放當(dāng)前頂點(diǎn)之間的最短路徑長度，其中B[i][j]表示當(dāng)前頂點(diǎn)i到j(luò)的最短路徑長度。依頂點(diǎn)編號(hào)順序處理每個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的處理看作一個(gè)階段，階段k（0≤k≤n-1）的結(jié)果存放在Bk中，Bk[i][j]表示處理完0～k的頂點(diǎn)后得到的頂點(diǎn)i到j(luò)的最短路徑長度。73/87階段k的處理過程：Bk-1[i][k]Bk-1[k][j]ijkBk-1[i][j]路徑①路徑②B-1[i][j]=A[i][j]Bk[i][j]=min0≤k≤n-1{Bk-1[i][j]，Bk-1[i][k]+Bk-1[k][j]}74/87intdp[MAXN][MAXN][MAXN];

//三維動(dòng)態(tài)規(guī)劃數(shù)組voidFloyd(vector<vector<int>>&A) //Floyd算法{ intn=A.size(); for(inti=0;i<n;i++) //求B(-1) for(intj=0;j<n;j++)

dp[0][i][j]=A[i][j]; for(intk=1;k<=n;k++) //依次求B(0)到B(n-1) { for(inti=0;i<n;i++) for(intj=0;j<n;j++)

dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k-1]+dp[k-1][k-1][j]); }}B-1[i][j]=A[i][j]Bk[i][j]=min0≤k≤n-1{Bk-1[i][j]，Bk-1[i][k]+Bk-1[k][j]}75/87階段k僅僅與階段k-1相關(guān)，因此可以將dp滾動(dòng)為dp[2][MAXN][MAXN]。階段k中求dp[k][i][j]時(shí)i和j的任意順序不影響最后的結(jié)果，進(jìn)一步將dp[2][MAXN][MAXN]滾動(dòng)為二維數(shù)組dp[MAXN][MAXN]intdp[MAXN][MAXN];

//二維動(dòng)態(tài)規(guī)劃數(shù)組voidFloyd(vector<vector<int>>&A) //Floyd算法{ intn=A.size(); for(inti=0;i<n;i++) //求B(-1) for(intj=0;j<n;j++)

dp[i][j]=A[i][j]; for(intk=0;k<n;k++) //依次求B(0)到B(n-1) { for(inti=0;i<n;i++) for(intj=0;j<n;j++)

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

}}76/878.4.2*雙機(jī)調(diào)度問題用兩臺(tái)處理機(jī)MA和MB加工n個(gè)作業(yè)，作業(yè)的編號(hào)為0～n-1，兩臺(tái)機(jī)器均可以加工任何作業(yè)。第i個(gè)作業(yè)單獨(dú)交給MA時(shí)的加工時(shí)間是a[i]，單獨(dú)交給MB時(shí)的加工時(shí)間是b[i]。現(xiàn)在要求每個(gè)作業(yè)只能由一臺(tái)機(jī)器加工，但兩臺(tái)機(jī)器在任何時(shí)刻可以加工兩個(gè)不同的作業(yè)。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，使得兩臺(tái)機(jī)器加工完所有n個(gè)作業(yè)的最短時(shí)間（從任何一臺(tái)機(jī)器開工到最后一臺(tái)機(jī)器停工的總時(shí)間）。例如，n=6，a

為（2，5，7，10，5，2），b為（3，8，4，11，3，4），結(jié)果為15。77/87解用maxA表示MA單獨(dú)加工所有作業(yè)的總時(shí)間，maxB表示MB單獨(dú)加工所有作業(yè)的總時(shí)間。設(shè)置一個(gè)三維動(dòng)態(tài)規(guī)劃數(shù)組dp，dp[k][A][B]表示前k個(gè)作業(yè)（作業(yè)編號(hào)為0到k-1）在MA用時(shí)不超過A且MB用時(shí)不超過B時(shí)是否有解。階段k考慮加工作業(yè)k-1，分為兩種情況：若A-a[k-1]≥0，作業(yè)k-1在機(jī)器MA上加工，則dp[k][A][B]=dp[k-1][A-a[k-1]][B]。若B-b[k-1]≥0，作業(yè)k-1在機(jī)器MB上加工，則dp[k][A][B]=dp[k-1][A][B-b[k-1]]。兩種情況中任何一種情況求出dp[k][A][B]為true，則dp[k][A][B]為true。78/87dp[0][A][B]=true 0≤A≤maxA，0≤B≤maxBdp[k][A][B]=dp[k-1][A-a[k-1]][B] 當(dāng)A-a[k-1]≥0，在MA上運(yùn)行dp[k][A][B]=(dp[k][A][B]||dp[k-1][A][B-b[k-1]]) 當(dāng)B-b[k-1]≥0，在MB上運(yùn)行狀態(tài)轉(zhuǎn)移方程當(dāng)求出dp后，dp[n][A][B]為true時(shí)表示存在一個(gè)這樣的解，則max(A，B)為這個(gè)解對(duì)應(yīng)的總時(shí)間。最后答案是在所有解中比較求出總時(shí)間最少的時(shí)間ans。79/87intn=6; //作業(yè)數(shù)inta[]={2,5,7,10,5,2};intb[]={3,8,4,11,3,4};booldp[MAXN][MAXA][MAXB];

//三維動(dòng)態(tài)規(guī)劃數(shù)組intschedule() //求解算法{ intmaxA=0,maxB=0; for(inti=0;i<n;i++) //求maxA和maxB { maxA+=a[i]; maxB+=b[i]; } memset(dp,0,sizeof(dp)); //初始化為false for(intA=0;A<=maxA;A++) { for(intB=0;B<=maxB;B++)

dp[0][A][B]=true;

//k=0時(shí)一定有解 }80/87 for(intk=1;k<=n;k++) { for(intA=0;A<=maxA;A++) { for(intB=0;B<=maxB;B++) { if(A-a[k-1]>=0) //在MA上加工

dp[k][A][B]=dp[k-1][A-a[k-1]][B]; if(B-b[k-1]>=0) //在MB上加工

dp[k][A][B]=(dp[k][A][B]||dp[k-1][A][B-b[k-1]]); } } }81/87 intans=INF; //存放最少時(shí)間 for(intA=0;A<=maxA;A++) //求ans for(intB=0;B<=maxB;B++) if(dp[n][A][B]) ans=min(ans,max(A,B)); returnans;}【算法分析】上述算法的時(shí)間復(fù)雜度為O(n×maxA×maxB)，空間復(fù)雜度為O(n×maxA×maxB)。是多項(xiàng)式級(jí)？82/87intn=6; //作業(yè)數(shù)inta[]={2,5,7,10,5,2};intb[]={3,8,4,11,3,4};booldp[2][MAXA][MAXB];

//三維動(dòng)態(tài)規(guī)劃數(shù)組intschedule() //求解算法{ intmaxA=0,maxB=0; for(inti=0;i<n;i++) //求maxA和maxB { maxA+=a[i]; maxB+=b[i]; } memset(dp,0,sizeof(dp)); //初始化為false for(intA=0;A<=maxA;A++) { for(intB=0;B<=maxB;B++) { dp[1][A][B]=false;

//k=1時(shí)初始化為false

dp[0][A][B]=true;

//k=0時(shí)一定有解 } } intc=0;上述算法中dp[k][*][*]僅僅與dp[k-1][*][*]相關(guān)，可以將dp改為滾動(dòng)數(shù)組，將第一維MAXN改為2。83/87 for(intk=1;k<=n;k++) { c=1-c; memset(dp[c],false,sizeof(dp[c])); //初始化dp[c]為false for(intA=0;A<=maxA;A++) { for(intB=0;B<=maxB;B++) { if(A-a[k-1]>=0) //在MA上加工

dp[c][A][B]=dp[1-c][A-a[k-1]][B]; if(B-b[k-1]>=0) //在MB上加工

dp[c][A][B]=(dp[c][A][B] ||dp[1-c][A][B-b[k-1]]); } } } intans=INF; //存放最少時(shí)間 for(intA=0;A<=maxA;A++) //求ans for(intB=0;B<=maxB;B++) if(dp[c][A][B]) ans=min(ans,max(A,B)); returnans;}84/87可以進(jìn)一步優(yōu)化空間，設(shè)置一維動(dòng)態(tài)規(guī)劃數(shù)組dp，dp[A]表示當(dāng)MA加工時(shí)間為A（0≤A≤maxA）時(shí)MB的最少加工時(shí)間。首先將dp的所有元素初始化為0。階段k：考慮加工作業(yè)k-1，分為兩種情況：當(dāng)A<a[k-1]時(shí)，只能在MB上加工，MA的加工時(shí)間仍然為A，MB的加工時(shí)間為dp[A]+b[k-1]，則dp[A]=dp[A]+b[k-1]。當(dāng)A≥a[k-1]時(shí)，作業(yè)k-1既可以由MA加工也可以由MB加工。由MA加工時(shí)，MA的加工時(shí)間變?yōu)锳-a[k-1]；由MB加工時(shí)，MB的加工時(shí)間為dp[A]+b[k-1]。取兩者中的最小值，則dp[A]=min(dp[A-a[k-1]]，dp[A]+b[k-1])。當(dāng)求出dp后，max(A，dp[A])為完成n個(gè)作業(yè)的一個(gè)解，問題的最后答案是在所有解中比較求出總時(shí)間最少的時(shí)間ans即可。85/87intn=6; //作業(yè)數(shù)inta[]={2,5,7,10,5,2};intb[]={3,8,4,11,3,4};intschedule() //求解算法{ intmaxA=0; for(inti=0;i<n;i++) //求maxA maxA+=a[i];

intdp[MAXA];

//一維動(dòng)態(tài)規(guī)劃數(shù)組 memset(dp,0,sizeof(dp)); //初始化為086/87 for(intk=1;k<=n;k++) { for(intA=maxA;A>=0;A--) { if(A<a[k-1]) //此時(shí)只能在MB上運(yùn)行

dp[A]=dp[A]+b[k-1]; else //否則取MA或者M(jìn)B上處理的最少時(shí)間

dp[A]=min(dp[A-a[k-1]],dp[A]+b[k-1]); } } intans=INF; //存放最少時(shí)間 for(intA=0;A<=maxA;A++) ans=min(ans,max(A,dp[A])); returnans;}【算法分析】算法時(shí)間復(fù)雜度為O(n×maxA)，空間復(fù)雜度為O(maxA)。87/8788/87思政案例第8章動(dòng)態(tài)規(guī)劃8.1動(dòng)態(tài)規(guī)劃概述8.2一維動(dòng)態(tài)規(guī)劃CONTENTS提綱8.3二維動(dòng)態(tài)規(guī)劃8.4三維動(dòng)態(tài)規(guī)劃8.5字符串動(dòng)態(tài)規(guī)劃8.6背包動(dòng)態(tài)規(guī)劃8.7樹形動(dòng)態(tài)規(guī)劃8.8區(qū)間動(dòng)態(tài)規(guī)劃89/648.5字符串動(dòng)態(tài)規(guī)劃字符串動(dòng)態(tài)規(guī)劃是指采用動(dòng)態(tài)規(guī)劃算法求解字符串的相關(guān)問題。說明90/648.5.1最長公共子序列問題一個(gè)字符串的子序列是指從該字符串中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后得到的字符序列。例如"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。給定兩個(gè)字符串a(chǎn)和b，稱字符串c是a和b的公共子序列，是指c同是a和b的子序列。該問題是求兩個(gè)字符串a(chǎn)和b的最長公共子序列（LCS）。91/64設(shè)計(jì)二維動(dòng)態(tài)規(guī)劃數(shù)組dp，其中dp[i][j]為（a0，a1，…，ai-1）和（b0，b1，…，bj-1）的最長公共子序列長度，求dp[i][j]的兩種情況下。解a0

a1…ai-2

ai-1(a)ai-1=bj-1b0

b1…bj-2

bj-1dp[i-1][j-1]dp[i][j]=dp[i-1][j-1]+1a0

a1…ai-2

ai-1(b)ai-1≠bj-1b0

b1…bj-2

bj-1dp[i][j-1]dp[i][j]=m