提高篇——?jiǎng)討B(tài)規(guī)劃專題(編輯修改稿)
2024-09-01 06:31 本頁面
【文章內(nèi)容簡(jiǎn)介】 解完畢后再選擇使用哪一個(gè)，而是通過一種策略直接選擇一個(gè)子問題去求解，沒被選擇的子問題直接拋棄。這種所謂“最優(yōu)選擇”的正確性需要用歸納法證明。而動(dòng)態(tài)規(guī)劃不管是采用自底向上還是自頂向下的計(jì)算方式，都是從邊界開始向上得到目標(biāo)問題的解（即考慮所有子問題）。 ? 貪心：壯士斷腕的決策，只要選擇，絕不后悔。 ? 動(dòng)態(tài)規(guī)劃：要看哪個(gè)選擇笑到最后，暫時(shí)領(lǐng)先說明不了問題。 最大連續(xù)子序列和 【 問題描述 】 給定一個(gè)數(shù)字序列 A1,A2,……,An,求i,j(1=i=j=n),使得 Ai+……+Aj最大，輸出這個(gè)最大和。 【 樣例 】 輸入： 2 11 4 13 5 2 輸出： 20 步驟 1：令狀態(tài) dp[i]表示以 A[i]作為末尾的連續(xù)序列的最大和（ A[i]必須作為末尾）。 那么 dp[0]=2 dp[1]=11 dp[2]=7 (11+(4)=7) dp[3]=20 (11+(4)+13=20) dp[4]=15 (11+(4)+13+(5)=15) dp[5]=13 (11+(4)+13+(5)+(2)=13) 于是轉(zhuǎn)換成求 dp[0],dp[1],…,dp[n1]中的最大值，想辦法求解 dp數(shù)組。 原序列： 2 11 4 13 5 2 步驟 2：因?yàn)?dp[i]以 A[i]結(jié)尾的連續(xù)序列，那么只有兩種情況： ? 這個(gè)最大和的連續(xù)序列只有一個(gè)元素，即A[i]。 dp[i]=A[i] ? 這個(gè)最大和的連續(xù)序列有多個(gè)元素，即從前面某處 A[p]開始 (pi)，一直到 A[i]結(jié)尾。dp[i]=dp[i1]+A[i] ? 狀態(tài)轉(zhuǎn)移方程： dp[i]=max{A[i],dp[i1]+A[i]} ? 邊界 dp[0]=A[0]，從小到大枚舉 i，即可得到整個(gè) dp數(shù)組。 includecstdio includealgorithm includecstdlib includeiostream using namespace std。 const int maxn=10010。 int A[maxn],dp[maxn]。//A[i]存放序列， dp[i]存放以 A[i]結(jié)尾的連續(xù)序列的最大和 int main(){ int n。 scanf(%d,amp。n)。//cinn。 for(int i=0。in。i++){//讀入序列 scanf(%d,amp。A[i])。//cina[i]。 } //邊界 dp[0]=A[0]。 for(int i=1。in。i++){ //狀態(tài)轉(zhuǎn)移方程 dp[i]=max(A[i],dp[i1]+A[i])。 } //dp[i]存放以 A[i]結(jié)尾的連續(xù)序列的最大和，需要遍歷 i得到最大的才是結(jié)果 int k=0。 for(int i=1。in。i++){ if(dp[i]dp[k]){ k=i。 } } printf(%d\n,dp[k])。//coutdp[k])endl。 system(pause)。 return 0。 } 狀態(tài)的無后效性 ? 當(dāng)前狀態(tài)記錄了歷史信息，一旦當(dāng)前狀態(tài)確定，就不會(huì)再改變，且未來的決策只能在已有的一個(gè)或若干個(gè)狀態(tài)的基礎(chǔ)上進(jìn)行，歷史信息只能通過已有的狀態(tài)去影響未來的決策。 ? 即每次計(jì)算狀態(tài) dp[i]，都只會(huì)設(shè)計(jì) dp[i1]，而不直接用到 dp[i1]蘊(yùn)含的歷史信息。 動(dòng)態(tài)規(guī)劃核心 ? 對(duì)動(dòng)態(tài)規(guī)劃可解的問題來說，總會(huì)有很多設(shè)計(jì)狀態(tài)的方式， 但并不是所有狀態(tài)都具有無后效性 ，因此必須設(shè)計(jì)一個(gè)擁有無后效性的狀態(tài)以及相應(yīng)的狀態(tài)轉(zhuǎn)移方程，否則動(dòng)態(tài)規(guī)劃就沒有辦法得到正確結(jié)果。事實(shí)上， 如何設(shè)計(jì)狀態(tài)和狀態(tài)轉(zhuǎn)移方程，才是動(dòng)態(tài)規(guī)劃的核心，而它們也是動(dòng)態(tài)規(guī)劃最難的地方 。 問題 A: 最大連續(xù)子序列 （時(shí)間限制 : 1 Sec 內(nèi)存限制 : 32 MB） ? 題目描述 ? 給定 K個(gè)整數(shù)的序列 { N1, N2, ..., NK }，其任意連續(xù)子序列可表示為{ Ni, Ni+1, ..., Nj }，其中 1 = i = j = K。最大連續(xù)子序列是所有連續(xù)子序列中元素和最大的一個(gè)，例如給定序列 { 2, 11, 4, 13, 5, 2 }，其最大連續(xù)子序列為 { 11, 4, 13 }，最大和為
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1