动态规划和备忘录法的区别
发布网友
发布时间：2022-03-24 06:02
共1个回答
热心网友
时间：2022-03-24 07:32
1 最优子结构性质
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2 重叠子问题性质
动态规划算法对每个问题只解一次，将其解保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法通常只需要多项式时间。
备忘录方法：
•用一个表格来保存已解决的子问题的答案，用的时候查表即可。
•采用的递归方式是自顶向下。
•控制结构与直接递归相同，区别在于备忘录方式为每个解过的子问题建立备忘录。
•初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问题的解答即可。
备忘录方法与动态规划和递归的区别：
1、动态规划是自低向上 ，备忘录方法是自顶向下，递归是自顶向下
2、动态规划每个子问题都要解一次，但不会求解重复子问题；备忘录方法只解哪些确实需要解的子问题；递归方法每个子问题都要解一次，包括重复子问题• 。
动态规划解矩阵连乘问题
#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++) //横坐标
{ int k=j+i-1; //纵坐标
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;
}追问简答题而已
