是自下而上动态规划递归？

Question

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

Answer 1

我们在动态规划中使用的方法实际上是inductive。可以将建设性归纳证明转换为递归算法或迭代算法。这只是品味的问题。例如。 memoization是一个递归实现，而对于每个memoized算法都有一个迭代的方法。

简单的例子是斐波纳契数。我们可以把它写迭代：

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]; 
    } 

他们两个都是动态编程和他们有相同的顺序。在某些情况下，递归更容易。在某些情况下，迭代速度更快。