Dynamic Programming

Concept

DP applies when a problem has overlapping subproblems and optimal substructure. Store each subproblem's answer so it is computed once.

Top-down: recursion + memoization. Bottom-up: fill a table from the smallest cases upward.

Steps: define the state, write the recurrence, set base cases, choose the iteration order, then optimise space.

Complexity

Code (Python)

def climb_stairs(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def coin_change(coins, amount):
    dp = [0] + [float("inf")] * amount
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

Remember

• “Count ways” or “min/max cost” → likely DP.
• Write the brute-force recursion first, then memoize.
• Most 1-D DP needs only the last two values.