What Is Dynamic Programming?

Remember, don't repeat

Dynamic programming (DP) is for problems where the same smaller problems come up again and again. Solve each smaller problem once, write the answer down, and reuse it.

Think of it like this: If someone writes 1+1+1+1+1 = ? on a board, you count: 5. If they add another “+1”, you don't count again – you remember 5 and say 6. That's DP.

Two ways to do it

from functools import lru_cache

@lru_cache(maxsize=None)            # top-down: recursion + memo
def fib_top(n):
    if n < 2:
        return n
    return fib_top(n - 1) + fib_top(n - 2)

def fib_bottom(n):                  # bottom-up: fill a table
    table = [0, 1] + [0] * max(0, n - 1)
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

print(fib_top(50), fib_bottom(50))

Output

12586269025 12586269025

The DP recipe

• State: what does dp[i] mean? (Say it in words!)
• Choice / transition: how is dp[i] built from smaller answers?
• Base case: the smallest answers you know directly.
• Answer: which entry of the table is the final answer?

Remember: DP works when a problem has overlapping subproblems (the same pieces repeat) and optimal substructure (the best answer is built from best answers to the pieces).