Introducing Dynamic Programming with Fibonacci Numbers
Learn how dynamic programming reduces time complexity by solving overlapping subproblems efficiently. Explore the properties of optimal substructure and overlapping subproblems through Fibonacci examples, and master memoization and tabulation techniques to optimize recursive algorithms.
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 the results of subproblems, just like in 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) ...