在斐波那契数列中找到第n个项
f(n)= f(n-1)+ f(n-2)可以通过内存在O(n)时间内求解。
一种更有效的方法是使用分而治之在log n时间内求解矩阵[[1,1]，[1,0]]的n次幂。
是否有类似的方法可以遵循
f(n)= f(n-1)+ f(n-x)+ f(n-x + 1)[x是某个常数]。
只需存储先前的x个元素，就可以在O(n)时间内解决。
是否有更好的方法来解决此递归。
最佳答案
正如您已经怀疑的那样，这将非常相似。使用x * x矩阵的n次方
|1 0 0 0 .... 1 1|
|1
| 1
| 1
| 1
| 1
...................
...................
| ... 1 0|
如果将此矩阵与向量相乘，这很容易理解
f(n-1), f(n-2), ... , f(n-x+1), f(n-x)
导致
f(n), f(n-1), ... , f(n-x+1)
矩阵求幂可以在O(log(n))的时间内完成(当x被认为是常数时)。
对于斐波那契递归，也有一个封闭的公式解决方案，请参见http://en.wikipedia.org/wiki/Fibonacci_number，以查找Binet或Moivre公式。