Write a dynamic programming algorithm to calculate the following the recursion function.

Question

Write a dynamic programming algorithm to calculate the following the recursion function.

exp * (n) = [3 * 8 ^ (n + 1) + 40 * 8 ^ (n – 2), n > 1

8.                                                  n=1

1.                                                  n=0]

Summary

If n is greater than one, the function Exp(n) = 3*8n-1 + 40*8n-2 is used.

if n=1; if n=2; if n=3;

if n=0, 1

For n=0, the output is 1, for n=1 it is 8, and for n=2 it is 64.

For evaluating the given function, a dynamic programming solution is provided.

Explanation

1. The function expo has been implemented, and a value of ‘n’ has been passed to it.
2. A lookup array of the desired size is declared.
3. The lookup elements at index 0 are filled with 1, while the lookup entries at index 1 are filled with 8, representing 80 and 81.
4. Then, for each ‘n’ value, the power of 8 values is required numerous times.
5. Instead of constantly recalculating the powers, as in dynamic programming, the prior computed results will be saved and used as and when needed.
6. As a result, the lookup is filled till ‘n’ is reached.
7. The value at the preceding index is used in each iteration of filling the lookup.
8. The array is then utilized to directly calculate the exp(n) values, with the result returned.

Code

#include <iostream>
using namespace std;
int lookup[50];
int expo(int n)
{
    lookup[0]=1;
    lookup[1]=8;
    if(n==0 || n==1)
    return lookup[n];
    for(int i=2;i<=n;i++){
        lookup[i]=lookup[n-1]*8;
    }
    return 3*lookup[n-1] + 40*lookup[n-2];
}
int main()
{
    cout<<"exp(1) = "<<expo(1)<<endl;
    cout<<"exp(2) = "<<expo(2)<<endl;
    cout<<"exp(3) = "<<expo(3)<<endl;
}

Output

Also, read check the python code below that doesn’t work properly, adjust it, and explain?