algorithm - 动态规划 : True or False

Question

我对动态规划有一个概念上的疑问:

In a dynamic programming solution, the space requirement is always at least as big as the number of unique sub problems.

我用斐波那契数列来思考:

f(n) = f(n-1) + f(n-2)

这里有两个子问题，如果输入为n，所需空间至少为O(n)。对吧？

但是，答案是错误的。

谁能解释一下？

Answer 1

答案确实是错误的。

例如，在您的斐波那契数列中，您可以使用 O(1) 空间的动态规划，只需记住最后两个数字:

fib(n):
   prev = current = 1
   i = 2
   while i < n:
      next = prev + current
      prev = current
      current = next
   return current

这是一种常见的做法，您不需要所有较小的子问题来解决较大的子问题，您可以丢弃其中的大部分并节省一些空间。