Dynamic Programming Introduction

Break problems into overlapping subproblems, remember results, avoid recomputation

Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing results.
Two approaches:

Memoization (top-down), recursion + cache

Tabulation (bottom-up), iterative, fill a table

DP applies when a problem has: (1) optimal substructure and (2) overlapping subproblems.

Exponential time: useless for large n⚠ Works but messy

# Naive recursion: O(2^n), recomputes everything
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
# fib(50) takes hours...

Linear time: handles n=10000 easily✓ Pythonic

# DP bottom-up: O(n) time, O(1) space
def fib(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
# fib(50) is instant

💡

Same problem, completely different scaling, DP eliminates redundant computation

Memoization pattern, top-down DPpython

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)

# Each subproblem computed exactly once
# Time: O(n), Space: O(n)
print(fib_memo(50))  # → 12586269025 (instant)

🤔Quick Check

What are the two key properties a problem must have to apply dynamic programming?

Practice Exercises

0/1 solved

Exercise 1 of 1easy

⏱ 00:00

Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways to reach the top of n stairs?
Expected output: 8

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next