Fibonacci Series Using Dynamic Programming in C++

In this article, we will find the Fibonacci Series using the dynamic programming approach. Fibonacci Series is very popular among mathematicians and there are many natural phenomena revolving around this series. So without wasting any time let’s jump to a brief introduction to the Fibonacci Series.

What Is A Fibonacci Series?

It is a very popular mathematical infinite sequence, in which the first two terms are 0 and 1, and the successive terms are evaluated as the sum of the last two terms. The first few terms of the series are as follows:

0, 1, 1, 2, 3, 5, 8, 13, 21, . . . .

Classical Solution To Fibonacci Series

The naive approach to finding a particular term of the Fibonacci Series is using recursion. In this method, we keep on evaluating the preceding terms until we hit the base case. However, this is not an optimal solution for real-world applications. It involves linear time computation for calculating any term of the series. The following example will help you understand this brute force approach.

Suppose we need to calculate the 7th term of the series.
Our Base case will be: 1st term = 0 and 2nd term = 1
In order to calculate the 7th term, we start from the 1st and the 2nd terms,
then we calculate the 3rd term by: A3 = A2 + A1 --> A3 = 1 + 0 = 1

Similarly,
A4 = A3 + A2 --> A4 = 1 + 1 = 2
A5 = A4 + A3 --> A5 = 2 + 1 = 3
A6 = A4 + A3 --> A6 = 3 + 2 = 5
A7 = A4 + A3 --> A5 = 5 + 3 = 8

Total Iterations: N - 2 = 7 - 2  = 5

It is very clear that this method is linear in nature. And for calculating each term we have to compute the last N – 2 terms first.

Fibonacci Series Using Dynamic Programming

The dynamic programming approach always stores the answer to the subproblems that we have already solved. Basically

• Initialize a dp vector globally with -1
• Update: dp[0] = 0, and dp[1] = 1
• Now to calculate the N_th term of the series
  • Check if the solution is already calculated or not
    • If the solution to this problem is already calculated, then simply return the solution
    • Else, calculate the solution by making a call on: dp[N] = fibonacci(N – 1) + fibonacci(N – 2).
    • Finally return this solution.
• This approach may look similar to the brute force one but, when calculating multiple terms of the Fibonacci Series, it is safe to assume that the algorithm is constant time algorithm.
• Because suppose we have to calculate the 7_th term of the series, then I end up evaluating and storing the first 7 terms of the series in my dynamic programming array.
• Now whenever I need any of the terms ranging from 1 to 7, I have constant time access to it.
• When working with multiple terms this algorithm becomes almost constant time algorithm.

Now let’s look at the C++ implementation of this algorithm and its performance in a C++ program.

Note: The dynamic programming method utilizes

C++ Program To Demonstrate The Algorithm

#include <iostream>
#include <vector>

using namespace std;

int fibonacci(vector <int> &dp, int n)
{
        // base case
        if(n == 0)
                return 0;

        if(dp[n] != 0)
                return dp[n];

        // otherwise
        // calculate the solution and store it
        dp[n] = fibonacci(dp, n - 1) + fibonacci(dp, n - 2);

        // finally return the solution
        return dp[n];
}

int main()
{
        cout << "Enter the highest order term you want to evaluate" << endl;
        int n;
        cin >> n;

        // declare the dynamic programming vector
        vector <int> dp(n, 0);
        dp[1] = 1;

        cout << "Term " << n << " of the Fibonacci Series is: " << fibonacci(dp, n - 1) << endl;
}

Output

Conclusion

Today we learned the effective method to evaluate the N_th term of the Fibonacci Series. We started by discussing the Fibonacci Series and the brute force approach to calculate each term. Later we implemented a more efficient dynamic programming-based algorithm and demonstrated its usage via a C++ program. That’s all for today, thanks for reading.