Introducing Dynamic Programming with Fibonacci Numbers
Get introduced to dynamic programming and its techniques.
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) ...