ascal動態(tài)規(guī)劃普及組(文件)
【正文】 開始直到 n進(jìn)行順推計算所有的 f[i] ? 最后輸出最大的 f[i] 某個階段 i的 f[i]求解 ? f[i]的子問題是哪些？ ? f[i]子問題的最優(yōu)解保存在哪里？ ? 如何根據(jù)子問題的最優(yōu)解推算父問題的最優(yōu)解？ 狀態(tài)轉(zhuǎn)移方程 ? F[i]=max{f[j]+1 | 必須滿足的是所有的a[j]都必須不小于 a[i]} 核心程序段 ? fillchar(f,sizeof(f),1)。 ? end?，F(xiàn)在要求設(shè)計一個程序，以求得正確的答案。 特殊到一般抽象出轉(zhuǎn)移方程 ? 顯然 f[I,j]這個最優(yōu)解肯定是在下列情形中產(chǎn)生的： ? f[j,j1]*Aj+1… Ai ? f[j+1,j1]*Aj+2… Ai ? …… ? f[i1,j1]*Ai ? 提煉出初步的轉(zhuǎn)移方程： ? f[I,j]=max{f[i1,j1]*(a[i1+1]… a[i]) | j=i1=i1} ?
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1