algorithm - 创建一个动态编程算法以使用四面体数计算斐波那契序列

我被要求创建一个动态编程算法，使用如下定义的四元数计算斐波那契数列的泛化：
t（0）=0，t（1）=1，t（2）=1，t（3）=2，递推关系t（n）=t（n-1）+t（n-2）+t（n-3）+t（n-4）
问题是，我不确定我的算法是否被视为“动态”算法，而仍然有（许多）输入值可以被多次计算以下是我所拥有的：

//n is the value being computed (Tn)
tetranacci(n)
    if n = 0 then
        return 0;
    else if n = 1 or n = 2 then
        return 1;
    else if n = 3 then
        return 2
    else
        return tetranacci(n - 1) + tetranacci(n - 2) + tetranacci(n - 3) + tetranacci(n - 4)

如果这是正确的，有人能为我澄清是什么使这个动态我在网上找不到严格的定义谢谢！

最佳答案

我想我已经搞清楚了。只需在计算值时使用数组存储值：

//n is the value being computed (Tn), A is an array containing already-computed values for n
tetranacci(n)
    if n = 0 then
        return 0;
    else if n = 1 or n = 2 then
        return 1;
    else if n = 3 then
        return 2
    else if A[n] != null
        return A[n]
    else
        A[n] = tetranacci(n - 1) + tetranacci(n - 2) + tetranacci(n - 3) + tetranacci(n - 4)
        return A[n]