algorithm - 为什么带缓存的优化斐波那契被描述为自上而下的解决方案？

Question

似乎是斐波那契算法的优化版本正在使用内存。
示例:

int cache[N] = {0};  

int fibonacci(int n) {  
  if(cache[n] != 0) return cache[n];    
  if(n ==1 || n == 2) cache[n] = 1;  
  else cache[n] = fibonacci(n - 1) + fibonacci(n - 2);  
  return cache[n];  
}   

这被描述为自上而下的解决方案。
但为什么？要找到 fibonacci(10)，我们需要递归调用所有较低的数字，直到达到 1 并开始累积。所以在我看来这是一种自下而上的方法。
为什么是从上到下？

Answer 1

自上而下或自下而上的方法没有正式的定义，但通常自上而下的方法是从一个更大的问题开始，将其分割为更小的部分，然后将较小问题的解决方案组合成原始问题的解决方案。自下而上的解决方案是从小问题的解决方案开始，逐步扩大规模，直到找到解决整个问题的解决方案。

您上面的功能使用了内存。由于该函数是递归的，它表现出典型的自上而下的模式，即从一个更大的问题开始，将其拆分成多个部分，然后将它们组合起来。而且，由于该函数缓存其结果，并且该缓存以从较小的项开始并逐渐增长到较大的项的方式填充，因此缓存似乎是自下而上运行的。

我以前没有听说过“自上而下”这个词，但我见过许多其他类似的算法，它们展示了一些自上而下的结构与自下而上的方法相结合。 LR 解析就是一个很好的例子 - 它自下而上地工作，以对最终自上而下结构的理解为指导。