去年算法作業(yè)答案-第三章分析題3-1設(shè)計(jì)一個(gè)On2時(shí)間找出由個(gè)數(shù)組成

第三章動(dòng)態(tài)規(guī)劃算法分析題3-1 設(shè)計(jì)一個(gè)O(n2)時(shí)間的算法，找出由n個(gè)數(shù)組成的序列的最長(zhǎng)單調(diào)遞增子序列(LongestIncreasingSubsequence)分析示當(dāng)以a[i]為單調(diào)遞增子序列最后一個(gè)元素時(shí)，所得最長(zhǎng)單調(diào)遞增子序列的長(zhǎng)b[i] i0k0kintLIS(vector<int>a,vector<int>b{

a[k]inti,for(i=0;i<n;++i{b[i]=for(j=0;j<i;++j{if(a[j]<a[i]&&b[j]+1>b[i])b[i]=b[j]+1;}} maxinumb //b數(shù)組的最大值即aLIS}n），該解法的時(shí)間復(fù)雜度為O(n2)。算法分析題3-2 將3.1中算法的計(jì)算時(shí)間縮減至O(nlogn)(提示：分析Li表示。易知：L1<=L2<=…<=Lm如果Li>Lj(i<j)，那么去掉以Lj結(jié)尾的遞增子序列的最后j-i個(gè)元素，得到一iak<=Lj<LiLii的遞aLLiLm，那么m就是最大單調(diào)子列的長(zhǎng)度。用下面的方法可以用來(lái)L。ai<L1雜度為logn，于是總的復(fù)雜度為O(nlogn)。算法實(shí)現(xiàn)題3-1獨(dú)立任務(wù)最優(yōu)調(diào)度問(wèn)2臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)。設(shè)第i個(gè)作業(yè)交給機(jī)器A處理時(shí)需要時(shí)間ai，若由機(jī)器B來(lái)處理，則需要時(shí)間bi。由于各作業(yè)的特點(diǎn)和機(jī)iaibij，aj<bj。22個(gè)作業(yè)。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，使得這2臺(tái)機(jī)器處理完這n個(gè)作業(yè)的時(shí)間最短（從任何一臺(tái)機(jī)器開(kāi)工到最后一太機(jī)器停工的總時(shí)間。研究(a1,a2,a3,a4,a5,a6)=(b1,b2,b3,b4,b5,b6)=分析T[i][kkAi時(shí)，B處理器所花費(fèi)的最小時(shí)間。例如，當(dāng)A處理機(jī)花費(fèi)時(shí)間等于0，即A沒(méi)有參與k就是k個(gè)任務(wù)的時(shí)間和，則：kT[0][k]T[i][k]min(T[ia[k]][k1],T[i][k1]KA處理機(jī)來(lái)做，B處理機(jī)不費(fèi)的最小時(shí)間。假如將第K個(gè)任務(wù)交給B處理機(jī)來(lái)做，A處理機(jī)不動(dòng)，這樣完KK-1個(gè)任務(wù)，A處理機(jī)花費(fèi)時(shí)間小i時(shí)，BKB處理機(jī)上花費(fèi)的時(shí)，即算法實(shí)現(xiàn)3-5乘法表問(wèn)定義與字母表{a,bc分析

依此乘法表，對(duì)任一定義于上的字符串，適當(dāng)?shù)募永ㄌ?hào)后得到一個(gè)表達(dá)式。例如，對(duì)于字符串x=bbbba，它的一個(gè)加括號(hào)表達(dá)式為(b(bb))(ba)。依乘法表，該表達(dá)式的值為a。試設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算加括號(hào)方式，使由x導(dǎo)出的加括號(hào)表達(dá)式的值為a。abcabbabcbacaccf[i][j][0]：字符串中第i個(gè)元素到第j個(gè)元素的子串表達(dá)式值為a的加括號(hào)方式數(shù)f[i][j][1]：字符串中第i個(gè)元素到第j個(gè)元素的子串表達(dá)式值為b的加括號(hào)方式數(shù)f[i][j][2]：字符串中第i個(gè)元素到第j個(gè)元素的子串表達(dá)式值為c的加括號(hào)方式數(shù)jfij0fik0*fik12fik1*fik12fik2*aik結(jié)果保存于f[0][n-1][0]算法實(shí)現(xiàn)題3-2編輯距離問(wèn)(1)刪除一個(gè)字符(2)一個(gè)字符(3)d(A,B)。試設(shè)計(jì)一個(gè)有效算法,2AB,計(jì)算出它們的編輯距離d(A,B)。分析設(shè)字符串 Bj的最短編輯距離，其中 Bj=b1,b2…bjai=bj，d[i][j]d[i1][jd[i][j]d[i1][j1]d[i][j]d[i1][j]d[i][j]d[i][j1]d[0