动态编程可以与递归一起使用吗？

Question

我理解为什么DP比简单的递归更有效.

但是,我知道DP是使用memoization技术的递归.

对于Fibonacci,像这样:

int DP[10000]; //initalized by 0

int f(int num){
    if (DP[num] != 0)
        return DP[num];

    DP[num] = f(num -1) + f(num - 2);
    return DP[num];
}

我总是以这种递归方式使用DP,并且它在ACM等算法问题上运行良好.

最近,我知道大多数人都不会以这种方式使用DP.

他们像这样使用DP:

int fib(int n)
{
  /* Declare an array to store Fibonacci numbers. */
  int f[n+1];
  int i;

  /* 0th and 1st number of the series are 0 and 1*/
  f[0] = 0;
  f[1] = 1;

  for (i = 2; i <= n; i++)
  {
      /* Add the previous 2 numbers in the series
         and store it */
      f[i] = f[i-1] + f[i-2];
  }

  return f[n];
}

此来源来自http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

---

我不知道这两种方式的区别.

他们有相同的时间复杂性吗？

另外,我想知道我的方式(递归+ memoization)可以称为DP吗？

在算法问题上使用我的DP方式有什么缺点吗？

Answer 1

另外,我想知道我的方式(递归+ memoization)可以称为DP吗？

我认为这是一个临界案例.Cormen等人的算法导论,第二版将您的方法(第347页)描述为"动态编程的变体",将其与前面章节的"普通动态编程"进行对比,并将其称为"记忆化" "或"memoized recursion".

在算法问题上使用我的DP方式有什么缺点吗？

在您的具体示例中,我认为最大的缺点是您需要O(n)堆栈空间,这可能是许多环境中的问题(堆栈空间通常比堆空间更有限).虽然你引用的普通DP版本仍然使用O(n)空间,但我认为如何从那里到仅使用O(1)空间的版本更为明显.(对于许多其他DP问题也是如此;例如,最大公共子序列问题仅需要O(m  +  n)空间,但是备忘的递归解决方案需要O(mn)空间.)

另一方面,在某些情况下,您的方法可能会更好,但实际上最终需要哪些子问题并不是那么明显.在这种情况下,memoized递归方法避免了解决不必要的情况.