动态编程(DP)中自顶向下与自底向上的区别
资料:
"自底向上:我们可以按从最小开始之顺序预先计算所有函数值来求任何类似函数的值,每一步使用先前已计算的值计算当前值.
自顶向下:我们实现递归程序存储每一个它所计算的值(正如它最末的步骤),并对这些值进行检验,以避免重新计算他们中任何一项(正如它最初的步骤).
"
提问:
自底向上的预先计算函数值是个怎样的过程呢?与自顶向下使用的存储方法有何不同呢?
问题可能太泛了点,以Fibonacci为例,自顶向下的方法如下:
int f(int i)
{
static int known[10000] = {0};
if( known[i] != 0 )return known[i];
int t = i;
if(i <0) return 0;
if(i> 1) t = f(i-1) + f(i-2);
return known[i] = t;
}
请给出自底向上的方法
[解决办法]
void f( int n )
{
int i;
int known[i]={0};
known[1]=1;
for( i=2; i <n; ++i )
known[i]=known[i-1]+known[i-2];
}
[解决办法]
迭代和递归的区别。
