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

Question

I have been asked to create a dynamic programming algorithm to compute a generalization of the Fibonacci sequence using Tetranacci numbers defined as follows:

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)

The problem is, I am unsure whether or not my algorithm is considered a "dynamic" algorithm, whereas there are still (many) input values that could be computed more than once. Here's what I have:

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

If this is correct can someone clarify for me what makes this dynamic? I'm having trouble finding a strict definition online. Thanks!

Answer 1

I think I got to the bottom of it. Simply use an array to store values as they are computed:

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