自下而上动态编程是递归的吗

Question

在这种方法中，计算较小的子问题并缓存结果，然后我们计算较大的子问题，我们使用缓存早期计算值的表中较小子问题的已计算优化值。那么，这种方法是递归的还是迭代的呢？

Answer 1

我们在动态编程中使用的方法实际上是归纳。可以将构造性归纳证明转化为递归算法或迭代算法。这只是品味的问题。例如，记忆化是一种递归实现，而对于每个记忆化算法都有一种迭代方法。

一个简单的例子是斐波那契数。可以迭代编写：

Fib (n)
{
F_1=F_2=1;
For i =3..n 
F_i = F_i-1 + F_i-2;
Return F_n;
}

可以递归地写：

Define array F of size n;
F [1]=F [2]=1;
Fib (n)
{
If (F [n-1]==0)
F [n-1] = Fib (n-1);
If (F [n-2]==0)
F [n-2] = Fib (n-2);
F [n]= F[n-2]+F [n-1];
Return  F[n];
}

它们都是动态程序设计，具有相同的顺序。在某些情况下，编写递归更容易。在某些情况下，迭代会更快。