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

29917015865

樣例輸出：6最長不上升子序列問題最長不上升子序列問題：

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