algorithm - 查找所提供序列的第 N 项

Question

f(0) = p

f(1) = q

f(2) = r

for n > 2

f(n) = af(n-1) + bf(n-2) + c*f(n-3) + g(n)

where g(n) = n* n* (n+1)

p,q,r,a,b,c 已给定问题是，如何找到这个系列的第 n 项。

请帮助我为此找到更好的解决方案。

我已经尝试使用递归来解决这个问题。但是这种方式很耗内存。

Answer 1

比递归更好的方法是 memoization .您只需要知道 f(n) 的最后三个值。伪代码中的解决方案可能如下所示:

if n == 0:
    return p
else if n == 1:
    return q
else if n == 2:
    return r
else:    
    f_n-3 = p
    f_n-2 = q
    f_n-1 = r
    for i from 3 to n:
        f_new = a * f_n-1 + b * f_n-2 + c * f_n-3 + g(n)
        fn-1 = fn-2
        fn-2 = fn-3
        fn-3 = f_new

return f_new

这样您就不需要递归调用该方法并将所有计算出的值保存在堆栈中，而只需在您的内存中保存 4 个变量。

这应该会计算得更快并且使用更少的内存。