Dynamic Programming

Back to Index

Use when: optimal substructure + overlapping subproblems. Brute force recursion has repeated states.

Signal words: maximum/minimum, number of ways, can you reach, longest/shortest subsequence.

Core Idea

1. Define what dp[i] (or dp[i][j]) represents
2. Find the recurrence: dp[i] in terms of previous states
3. Identify base cases
4. Decide order of computation (top-down memo vs bottom-up tabulation)

Thought Process

• What decision is made at each step?
• What state do I need to capture to make that decision?
• Can I reduce state dimensions?

1D Template

dp = [0] * (n + 1)
dp[0] = <base case>
for i in range(1, n + 1):
    dp[i] = <recurrence using dp[i-1], dp[i-2], etc.>
return dp[n]

2D Template

dp = [[0] * (m + 1) for _ in range(n + 1)]
# fill base cases: dp[0][j] and dp[i][0]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = <recurrence>
return dp[n][m]

Common Subtypes

• Knapsack: include/exclude an item
• LCS / Edit Distance: 2D string comparison
• Interval DP: dp[i][j] = answer for subarray [i..j]
• State machine DP: track mode (e.g., holding stock or not)

---

Problems Using This Pattern