递归可以动态编程吗？

Question

我被要求使用动态编程来解决问题。我对构成动态编程的观点有好有坏。我相信这需要“自下而上”的方法，首先解决最小的问题。

我有一个矛盾的信息，就是如果相同的子问题不止一次被解决，那么某些事情是否可以是动态编程，这在递归中很常见。

例如。对于斐波那契，我可以有一个递归算法：

RecursiveFibonacci(n)
if (n=1 or n=2)
    return 1
else
    return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2)

在这种情况下，相同的子问题可能会一遍又一遍地解决。这是否使它成为not动态编程？也就是说，如果我想进行动态编程，我会（不得不）避免解决子问题，例如使用长度为n的数组并将解决方案存储到每个子问题（数组的第一个索引为1、1、2， 3，5，8，13，21）？

Fibonacci(n)
F1 = 1
F2 = 1
for i=3 to n
    Fi=Fi-1 + Fi-2
return Fn

我被要求使用动态编程来解决问题。我对构成动态编程的观点有好有坏。我认为这需要一种“自下而上”的方法，可以解决最小的问题...

Answer 1

动态程序通常可以用递归公式简要描述。

Answer 2

我们认为有问题的动态编程方法