算法設(shè)計(jì)與分析 課件 5.7-動(dòng)態(tài)規(guī)劃應(yīng)用-最長(zhǎng)不上升子序列

信息工程大學(xué)算法設(shè)計(jì)與分析動(dòng)態(tài)規(guī)劃—最長(zhǎng)不上升子序列國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版某國(guó)為了防御敵國(guó)導(dǎo)彈襲擊，開發(fā)出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲，由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈的枚數(shù)和導(dǎo)彈依次飛來(lái)的高度，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈？樣例輸入：8389207155300

29917015865

樣例輸出：6最長(zhǎng)不上升子序列問(wèn)題最長(zhǎng)不上升子序列問(wèn)題：

設(shè)有一個(gè)正整數(shù)的序列a0,a1,…,an-1,對(duì)于下標(biāo)i1<i2<…＜im，若有ai1>=ai2>=…>=aim，則稱存在一個(gè)長(zhǎng)度為m的不上升子序列。當(dāng)a0,a1,…,an-1給出之后，求最長(zhǎng)不上升子序列的長(zhǎng)度。i01234567a[i]38920715530029917015865問(wèn)題分析：a[8]={389,207,155,300,299,170,158,65}i=0時(shí)，{389}，長(zhǎng)度為1i=1時(shí)，{389207}，長(zhǎng)度為2i=2時(shí)，{389207155}，長(zhǎng)度為3i=3時(shí)，{389300}，長(zhǎng)度為2……如果a[j]>=a[i]且j<i，那么以a[i]為結(jié)尾元素構(gòu)成的不上升子序列長(zhǎng)度=以a[j]為結(jié)尾元素構(gòu)成的不上升子序列長(zhǎng)度+1；a[i]為結(jié)尾元素構(gòu)成的最長(zhǎng)不上升子序列長(zhǎng)度=max{以a[j]為結(jié)尾元素構(gòu)成的最長(zhǎng)不上升子序列長(zhǎng)度+1}問(wèn)題分析：定義f(i)表示以a[i]結(jié)尾的最長(zhǎng)不上升子序列的長(zhǎng)度。f(i)=max{f(j)+1}，且j<i，a[j]≥a[i]，0≤j<i<n。最長(zhǎng)不上升子序列長(zhǎng)度為max{f(i)}(0≤i≤n-1)。i01234567a[i]38920715530029917015865f[i]最優(yōu)值的計(jì)算過(guò)程：f(i)=max{f(j)+1}，且j<i，a[j]≥a[i]，0≤j<i<n。12323456整個(gè)問(wèn)題的解為：max{f(i)}=6fori=0ton-1f[i]=1;/*初始化*/fori=1ton-1/*分階段求f[i]*/{maxlen=1;forj=0toi-1if(a[i]<=a[j]&&f[j]+1>maxlen)maxlen=f[j]+1;f[i]=maxlen;}maxlen=f[0];/*求最優(yōu)值*/fori=1ton-1iff[i]>maxlenmaxlen=f[i];printf(maxlen);時(shí)間復(fù)雜度T(n)=O(n2)思考：如何求解對(duì)應(yīng)的最優(yōu)解？設(shè)s(i)記錄f(i)對(duì)應(yīng)的j，即a[i]前面的一項(xiàng)為a[j]。從最大的f(i)開始，根據(jù)s(i)不斷得到其前面的若干項(xiàng)。最終得到38930029917015865i01234567a[i]38920715530029917015865f[i]12323456s[i]-10