algorithm - 自底向上动态规划是递归的吗？

Question

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

Answer 1

我们在动态规划中使用的方法实际上是归纳的。可以将建设性归纳证明转换为递归算法或迭代算法。这只是口味问题。例如，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];
  }

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