AI Hints
Home›DSA in Python Tutorial›Greedy Algorithms
DSA in Python · Lesson 90 of 132

Dynamic Programming

Solve each small problem once.

⏱ 2 min read▶ Video at 1:47:29🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Dynamic programming sounds intimidating, but it's just two ideas you've already met. Break a problem into smaller versions of itself, like recursion. And save each answer, so you never solve the same small problem twice, like memoization.

Dynamic Programming
From the video: Dynamic Programming
  • Sounds scary
  • Smaller versions of the problem
  • Save each answer

Two styles

There are two styles. Top down starts with the big problem, recurses into smaller ones, and caches the answers, exactly like our fast Fibonacci. Bottom up starts with the tiniest problems, and fills in a table, step by step, until it reaches the big one. Both give the same answers, in the same Big O.

Top downrecursion + cache
Bottom upfill a table
Key questionwhat's the smaller problem?
Same speedusually

Fibonacci, bottom up

Here's Fibonacci, bottom up. We start a table with the first two answers, zero and one. Each new entry is the sum of the two before it. No recursion, no cache, just a loop. Run it. Fib of ninety is instant.

fib_table.pypython
def fib(n):
    table = [0, 1]
    for i in range(2, n + 1):
        table.append(table[i - 1] + table[i - 2])
    return table[n]

print(fib(10), fib(90))
Output
55 2880067194370816120

Summary

Dynamic programming solves each small problem once, top down with a cache, or bottom up with a table. Next, a classic. Climbing stairs.

Key takeaways
  • Smaller problems
  • Save each answer
  • Top down or bottom up
Next up: Practice: Climbing Stairs — counting the ways