Dynamic Programming

When to use

Use when a problem has overlapping subproblems — you'd compute the same state multiple times in a naive approach. Also when you need to find the optimal (max/min/count) of something across choices.

Core intuition

Define a state that captures everything relevant at a point in the problem. Write a recurrence: how does dp[i] relate to dp[i-1] or dp[i][j-1]? Then either memoize top-down or fill a table bottom-up.

Template

# Top-down memoization
from functools import lru_cache
def solve(n):
    @lru_cache(maxsize=None)
    def dp(i):
        if i <= 1:
            return i
        return dp(i-1) + dp(i-2)
    return dp(n)

# Bottom-up tabulation
def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Suggested problems