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, . . . .

General Formula: An = An-1 + An - 2

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.

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 Dynamic Programming = Memoization + Recursion. Hence, we’ll find the Nth term of the Fibonacci Series using the terms we’ve already calculated(Never solve the same problem again and again, instead remember the solution and just use it whenever needed). To make this happen, we will follow the following approach.

• Initialize a dp vector globally with -1
• Update: dp[0] = 0, and dp[1] = 1
• Now to calculate the Nth 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 7th 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 O(N) extra space for storing the intermediate states(Repeating Subproblems).

C++ Program To Demonstrate The Algorithm

Dynamic Programming Fibonacci Code

Output

Fibonacci Series Output

Conclusion

Today we learned the effective method to evaluate the Nth 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.

Further Readings

To learn more about dynamic programming, you can refer to the following websites.

https://www.journaldev.com/56866/solving-0-n-knapsack-problem-in-cpp

https://www.journaldev.com/56918/0-1-knapsack-using-cpp