问题： 使用带有记忆功能的前向递归计算第 n 个斐波那契数有意义吗？
背景：大多数学习资源和书籍（例如 CLRS、DPV 等）都使用所谓的向后递归介绍动态规划 (DP)，我们从目标开始并朝着基本情况努力，但是 前向递归而是从基本情况开始并朝着目标努力（这将在Codeforces以及OR上进一步讨论）堆栈交换）。 例如，
入室抢劫者是一个经典问题，DP 解决方案是有意义的。我们可以通过以下方式使用带有记忆功能的后向递归：
def rob(nums):
def dp(house):
if house <= 1:
return max(nums[:house+1])
if house in memo:
return memo[house]
memo[house] = max(nums[house] + dp(house - 2), dp(house - 1))
return memo[house]
memo = dict()
return dp(len(nums) - 1)
或者我们可以使用带有记忆功能的forward
递归，如下所示：
def rob(nums):
def dp(house):
if house >= n:
return 0
if house in memo:
return memo[house]
memo[house] = max(nums[house] + dp(house + 2), dp(house + 1))
return memo[house]
n = len(nums)
memo = dict()
return dp(0)
这些方法反映了对同一想法的不同思考方式。对于前向递归，我们按时间顺序思考我们从哪里开始以及我们从那里有什么选择（例如，是抢劫还是跳过第一间房子）。对于向后递归，我们首先考虑整个解决方案以及导致我们实现目标的最后一个选择（例如，我们是否抢劫或跳过了最后一个房子）。上面代码片段之间的实际区别在于索引到处翻转，目标和基本情况位于相反的两端。
这给我们带来了斐波那契数列和这个问题的目的。通过带有记忆功能的后向递归计算第 n 个斐波那契数非常简单：
def fib(n):
def dp(i):
if i < 2:
return i
if i in memo:
return memo[i]
memo[i] = dp(i - 1) + dp(i - 2)
return memo[i]
memo = dict()
return dp(n)
“到处翻转索引”并使目标和基本情况处于相反的两端意味着什么？对于斐波那契数，基本情况正是
F_0 = 0和
F_1 = 1前两个斐波那契数之和。那么，尝试使用带有记忆功能的前向递归来计算第 n 个斐波那契数会是什么样子？ 以下是一种可能的尝试：
def fib(n):
def dp(i):
if i >= n:
return i - n
if i in memo:
return memo[i]
memo[i] = dp(i + 1) + dp(i + 2)
return memo[i]
memo = dict()
return dp(0)
这个片段有效，但看起来非常不自然。它会导致一些奇怪的事情，例如计算
memo[n - 1] = dp(n) + dp(n + 1)，从而导致让
dp(n) = 0dp(n + 1) = 1有人对这一切有很好的解释吗？似乎有些问题自然适合向后DP，尤其是那些很容易用直接递推关系表达的问题。但对于斐波那契数列，带有记忆功能的前向递归似乎甚至没有意义，因为每个数字都是“定义”的，是直接递归关系的结果，其中每个数字被定义为前两个数字的总和。当内在关系本质上是向后的、一开始就有基本情况并且关系在正方向上无限制地延伸时，前向递归通常没有多大意义吗？或者我完全误解了“向后”和“向前”递归的含义？ 使用前向 DP，您需要付出额外的努力来确保您的算法不会计算超出严格需要的内容。
一个例子，计算帕斯卡三角形的
(i+1,j+1)项。最简单和最简单的前向算法将计算整个三角形，直到并包括第
j行。
但是后向算法只会计算三角形中所需的“菱形”面积，这一切都是靠它自己的孤独。