创建一个动态编程算法以使用 tetranacci 数计算斐波那契数列

Question

我被要求创建一个动态规划算法来使用定义如下的 Tetranacci 数来计算斐波那契数列的泛化：

T(0) = 0, T(1) = 1, T(2) = 1, T(3) = 2, and the recurrence relation T(n) = T(n - 1) + T(n - 2) + T(n - 3) + T(n - 4)

问题是，我不确定我的算法是否被认为是 "dynamic" 算法，而仍然有（许多）输入值可以计算多次。这是我拥有的：

//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)

如果这是正确的，有人可以为我解释一下是什么让这种动态发生吗？我在网上找不到严格的定义。谢谢！

Answer 1

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

//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]

Answer 2

在C#中完全不用递归调用也可以实现动态规划算法如下

int Tetranacci(int n)
{
    var NumOfStates = Math.Max(n + 1, 4);  // accomodate enough space
    var States = new int[NumOfStates];     // to contain all initial values
    States[0] = 0;                         // initialize first states
    States[1] = 1;
    States[2] = 1;
    States[3] = 2;
    for (int i = 4; i < n; i++)            // iterate up to desired value
    {
        States[i] = States[i-1] + States[i-2] + States[i-3] + States[i-4];
    }
    return States[n];
}

创建一个动态编程算法以使用 tetranacci 数计算斐波那契数列

Create a dynamic programming algorithm to compute the fibonacci sequence using tetranacci numbers

algorithm

recursion

dynamic

pseudocode

divide-and-conquer