备忘录方法与动态规划比较
?動(dòng)態(tài)規(guī)劃算法的基本要素：?
1? 最優(yōu)子結(jié)構(gòu)性質(zhì)
當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
2? 重疊子問(wèn)題性質(zhì)???
動(dòng)態(tài)規(guī)劃算法對(duì)每個(gè)問(wèn)題只解一次，將其解保存在一個(gè)表格中，當(dāng)再次需要解此問(wèn)題時(shí)，用常數(shù)時(shí)間查看一下結(jié)果。因此，用動(dòng)態(tài)規(guī)劃算法通常只需要多項(xiàng)式時(shí)間。
備忘錄方法：
?用一個(gè)表格來(lái)保存已解決的子問(wèn)題的答案，用的時(shí)候查表即可。?
?采用的遞歸方式是自頂向下。
?控制結(jié)構(gòu)與直接遞歸相同，區(qū)別在于備忘錄方式為每個(gè)解過(guò)的子問(wèn)題建立備忘錄。?
?初始化為每個(gè)子問(wèn)題的記錄存入一個(gè)特殊的值，表示并未求解。在求解過(guò)程中，查看相應(yīng)記錄如果是特殊值，表示未求解，否則只要取出該子問(wèn)題的解答即可。
備忘錄方法與動(dòng)態(tài)規(guī)劃和遞歸的區(qū)別：
1、動(dòng)態(tài)規(guī)劃是自低向上 ，備忘錄方法是自頂向下，遞歸是自頂向下
2、動(dòng)態(tài)規(guī)劃每個(gè)子問(wèn)題都要解一次，但不會(huì)求解重復(fù)子問(wèn)題；備忘錄方法只解哪些確實(shí)需要解的子問(wèn)題；遞歸方法每個(gè)子問(wèn)題都要解一次，包括重復(fù)子問(wèn)題??。
動(dòng)態(tài)規(guī)劃解矩陣連乘問(wèn)題
#include<iostream>
using namespace std;
void metrixchain(int n,int p[],int **s,int **m)
{
?for(int i=0;i<n;i++)
? m[i][i]=0;
?for(i=2;i<=n;i++)??? //小于等于n
?{
? for(int j=0;j<n-i+1;j++) //橫坐標(biāo)
? { int k=j+i-1;?? //縱坐標(biāo)
? m[j][k]=m[j+1][k]+p[j]*p[k+1]*p[j+1];s[j][k]=j;
? for(int t=j+1;t<k;t++)
? {
?? int u=m[j][t]+m[t+1][k]+p[j]*p[t+1]*p[k+1];
?? if(u<m[j][k])
?? {
??? m[j][k]=u;s[j][k]=t;
?? }
? }
? }
?}
}
void Traceback(int i, int j, int ** s)
{
?if (i==j||i==j-1) return;
?cout<<"divide after metrix "<<s[i][j]<<endl;
?Traceback(i, s[i][j],? s);
?Traceback(s[i][j]+1,j ,? s);
}
int main()
{
?int p[]={30,35,15,5,10,20,25};
?int **s=new int*[6];
?for(int i=0;i<6;i++)
? s[i]=new int[6];
?int **m=new int*[6];
?for( i=0;i<6;i++)
? m[i]=new int[6];
?metrixchain(6,p,s,m);
?for( i=0;i<6;i++)
?{ for( int j=i;j<6;j++)
?cout<<m[i][j]<<" ";
?cout<<endl;
?}
?Traceback(0,5,s);
?return 0;
}
總結(jié)
以上是生活随笔為你收集整理的备忘录方法与动态规划比较的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
