Dynamic programming

Reach for it when

• Climbing stairs / house robber (1-D)
• Knapsack and coin change (2-D or rolled 1-D)
• Edit distance and LCS (grid)
• Longest increasing subsequence (patience / binary search variant)
• Interval DP: burst balloons, matrix chain

Reference implementation

def coin_change(coins: list[int], amount: int) -> int:
    """Fewest coins summing to amount, or -1."""
    INF = float("inf")
    # dp[a] = fewest coins to make exactly a
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] + 1 < dp[a]:
                dp[a] = dp[a - coin] + 1
    return -1 if dp[amount] == INF else int(dp[amount])

Complexity: states × transition cost. Coin change is O(amount × coins).

What goes wrong

• Iterating coins in the outer loop and amount descending — that is 0/1 knapsack, not unbounded.
• Initialising dp with 0 instead of infinity, so unreachable amounts silently look reachable.
• Using a mutable default or `[[0] * n] * m` — the rows alias each other.

Practise on

• Coin Change
• House Robber
• Edit Distance
• Longest Increasing Subsequence
• Partition Equal Subset Sum