建设网站需要什么知识/今日新闻简报
如果一个递归
动态规划的具体实现可以分为两类：一类是自顶向下的备忘录方法，这种方法只需要对原始的递归算法进行少量的改动，增加一个子问题解的记录，每当需要用到一个子问题的解时，首先查看这个记录，如果记录中存在需要的解，则可直接得到，如果不存在，则递归求解，并将结果记录下来。另一类是自底向上的迭代方法，这种方法从最基本的子问题开始求解，并将结果记录下来，然后利用已经求得的解继续对高一级的子问题求解，这样循环计算下去，直到解决了最终的问题为止。
斐波那契数列是一个体现动态规划方法的简单问题，下面分别给出原始递归算法、备忘录方法和迭代方法的源码。
原始递归算法，该算法需要大量重复计算相同子问题：
int fab(int n)
{
if(n == 0 || n == 1){
return 1;
}
else{
return fab(n - 1) + fab(n - 2);
}
}
动态规划的备忘录方法：#define SIZE 50
int fab(int n, int m[])
{
if(m[n]){
return m[n];
}
else{
m[n] = fab(n - 1, m) + fab(n - 2, m);
return m[n];
}
}
int memFab(int n)
{
int m[SIZE];
int i;
m[0] = 1;
m[1] = 1;
for(i = 2; i < SIZE; ++i){
m[i] = 0;
}
return fab(n, m);
}
动态规划的迭代方法：int fab(int n)
{
int f1, f2, f3, i;
if(n == 0 || n == 1){
return 1;
}
else{
f1 = 1;
f2 = 1;
for(i = 1; i < n; ++i){
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}
}