Fibonacci Sequence: The Dynamic Programming Algorithm
Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. The series of subproblems is conceived in a manner that permits a subsequent subproblem to be solved by combining the solutions of one or more of the subproblems already solved - making dynamic programming a bottom-up approach. When applicable, the method takes far less time than naive methods that don't take advantage of the subproblem overlap.
The dynamic programming version of the fibonacci algorithm runs in linear time, O(N). In this algorithm, we keep track of two consecutive Fibonacci numbers and use them in order to compute the next Fibonacci number. The code is as follows: