Introducing Dynamic Programming with Fibonacci Numbers
In this lesson, we'll use a dynamic programming technique called memoization to reduce the time complexity of the Fibonacci function.
We'll cover the following
We are now going to use a dynamic programming technique to reduce the time complexity to linear.
What is dynamic programming?
Dynamic programming algorithms solve problems by combining results of subproblems, just like in the divide and conquer algorithms.
Characteristics
Most problems that can be solved with dynamic programming can also be solved with a divide and conquer approach. The difference between the two is that the dynamic programming approach is applicable when a problem has overlapping subproblems; i.e. the subproblems of a given problem are not independent such as when two subproblems share a sub-subproblem. An example would be the Fibonacci code we saw in the last lesson where fib(3) had to be calculated in order to calculate both fib(4) and fib(5).
Furthermore, dynamic programming problems have the optimal substructure property, which means that the overall optimal solution of the problem can be constructed from the optimal solutions of its subproblems. For Fibonacci numbers, we know that,
fib(n) = fib(n-1) + fib(n-2)
Hence, a problem of size ‘n’ can be reduced to subproblems of size ‘n-1’ and ‘n-2’. Therefore, Fibonacci numbers have the optimal substructure property.
Dynamic programming algorithms solve every subproblem just once and save the answer in a lookup table, thereby avoiding recalculating the answer every time the subproblem is encountered.
There are two dynamic programming patterns: memoization and tabulation.
Memoization (top-down)
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.