DP Patterns Overview (When to Use DP)

This meta-skill ties together patterns: knapsack, LIS, interval DP, digit DP, bitmask DP—pick state that encodes just enough history.

Why this shows up in the real world

Interview ladders group problems by state shape. Product features reuse DP for small combinatorial configs.

Core idea (explained for students)

Practice mapping story → state variables → transition order; keep a personal pattern library.

Try this in Python

def fib(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]


print(fib(30))

Common mistakes

• Overfitting one template to mismatched problems.
• Under-specifying base cases.

Key takeaways

• Re-solve classics monthly to retain muscle memory.