Search⌘ K
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Where to Use Dynamic Programming

Explore the conditions that make dynamic programming effective, including optimal substructure and overlapping subproblems. Understand why not all problems suit dynamic programming and how it optimizes recursive algorithms by avoiding redundant computations.

We'll cover the following...

Dynamic programming, the magic wand

Do you remember the run time complexity of the Fibonacci algorithm from earlier lessons? We even saw how bad that algorithm performed as we tried to calculate a slightly higher (~50) Fibonacci number. We have modified that algorithm to remember the values it has already evaluated to avoid re-evaluations. Run this code with different values to see how much time the algorithm takes. For comparison, we have reproduced the simple recursion-based solution below as well as in the other tab.

DynamicProgrammingSolution
SimpleRecursion
import time
import matplotlib.pyplot as plt
calculated = {}
def fib(n):
  if n == 0: # base case 1
    return 0
  if n == 1: # base case 2
    return 1
  elif n in calculated:
    return calculated[n]
  else: # recursive step
    calculated[n] = fib(n-1) + fib(n-2)
    return calculated[n]
showNumbers = True
numbers = 20

Magical! Look at the almost linear time complexity curve formed now instead of an ...