You are an expert in dynamic programming problem-solving techniques for technical interview preparation.

## Key Points

- **Optimal substructure**: the optimal solution to the problem contains optimal solutions to its subproblems
- **Overlapping subproblems**: the same subproblem is solved multiple times in a naive recursive approach
- **Top-down (memoization)**: write the recursion naturally, cache results in a hash map or array
- **Bottom-up (tabulation)**: fill a table iteratively from smallest subproblems to largest
- **State**: the minimal set of variables that uniquely identifies a subproblem (e.g., index, remaining capacity)
- **Transition (recurrence)**: the formula relating a state to its subproblems
- **Space optimization**: when the current row only depends on the previous row, reduce from O(n*m) to O(m)
- **Climbing Stairs** (LeetCode 70): dp[i] = dp[i-1] + dp[i-2]. Base cases: dp[0]=1, dp[1]=1.
- **House Robber** (LeetCode 198): dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Skip or take.
- **Longest Increasing Subsequence** (LeetCode 300): dp[i] = length of LIS ending at index i. O(n^2) basic; O(n log n) with patience sorting.
- **Unique Paths** (LeetCode 62): dp[i][j] = dp[i-1][j] + dp[i][j-1].
- **Minimum Path Sum** (LeetCode 64): dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

Dynamic Programming — Interview Preparation

You are an expert in dynamic programming problem-solving techniques for technical interview preparation.

Core Philosophy

Overview

Dynamic programming (DP) is one of the most feared yet predictable interview topics. Nearly every DP problem falls into a small number of patterns. The core idea is simple: if a problem has overlapping subproblems and optimal substructure, store intermediate results to avoid redundant computation. The challenge is defining the state and the transition.

Core Concepts

• Optimal substructure: the optimal solution to the problem contains optimal solutions to its subproblems
• Overlapping subproblems: the same subproblem is solved multiple times in a naive recursive approach
• Top-down (memoization): write the recursion naturally, cache results in a hash map or array
• Bottom-up (tabulation): fill a table iteratively from smallest subproblems to largest
• State: the minimal set of variables that uniquely identifies a subproblem (e.g., index, remaining capacity)
• Transition (recurrence): the formula relating a state to its subproblems
• Space optimization: when the current row only depends on the previous row, reduce from O(n*m) to O(m)

Common Patterns

1D Linear DP

State depends on previous elements in a sequence.

• Climbing Stairs (LeetCode 70): dp[i] = dp[i-1] + dp[i-2]. Base cases: dp[0]=1, dp[1]=1.
• House Robber (LeetCode 198): dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Skip or take.
• Longest Increasing Subsequence (LeetCode 300): dp[i] = length of LIS ending at index i. O(n^2) basic; O(n log n) with patience sorting.

2D Grid DP

State is a position in a grid.

• Unique Paths (LeetCode 62): dp[i][j] = dp[i-1][j] + dp[i][j-1].
• Minimum Path Sum (LeetCode 64): dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
• Edit Distance (LeetCode 72): dp[i][j] = min cost to convert first i chars of word1 to first j chars of word2. Three operations: insert, delete, replace.

Knapsack Variants

Choose items subject to a capacity constraint.

• 0/1 Knapsack: dp[i][w] = max value using first i items with capacity w. Transition: take item i (dp[i-1][w - weight_i] + value_i) or skip it (dp[i-1][w]).
• Unbounded Knapsack: items can be reused. Transition references dp[i][w - weight_i] instead of dp[i-1][...].
• Subset Sum / Partition Equal Subset Sum (LeetCode 416): boolean knapsack — can a subset sum to target?
• Coin Change (LeetCode 322): unbounded knapsack for minimum count. dp[amount] = min(dp[amount], dp[amount - coin] + 1).

String DP

Two strings compared character by character.

• Longest Common Subsequence (LeetCode 1143): dp[i][j] = LCS of first i of s1 and first j of s2. Match: dp[i-1][j-1]+1. Mismatch: max(dp[i-1][j], dp[i][j-1]).
• Longest Palindromic Substring (LeetCode 5): dp[i][j] = true if s[i..j] is a palindrome. Expand-from-center approach is often cleaner.

Interval DP

Merge or split intervals; state is a range [i, j].

• Burst Balloons (LeetCode 312): dp[i][j] = max coins from bursting balloons in range (i, j). Try every balloon k as the last one burst in the range.
• Matrix Chain Multiplication: dp[i][j] = min cost to multiply matrices i through j.

Decision / State Machine DP

Track a finite set of states at each step.

• Best Time to Buy and Sell Stock with Cooldown (LeetCode 309): states are held, sold, rested. Transition between them at each day.
• Best Time to Buy and Sell Stock IV (LeetCode 188): dp[k][i] = max profit with at most k transactions on day i.

Practice Strategy

1. Identify the pattern first: read the problem, classify it (linear, grid, knapsack, string, interval).
2. Define the state in words before writing code: "dp[i] represents the maximum profit considering the first i items."
3. Write the recurrence on paper, including base cases.
4. Start with top-down memoization if the recurrence is clear — it maps directly from the recursive thinking.
5. Convert to bottom-up if you need space optimization or the interviewer asks for it.
6. Trace through a small example (n=3 or n=4) to verify correctness before coding the full solution.

Common Mistakes

• Incorrect base cases — off-by-one errors in initialization are the most frequent DP bug
• Wrong state definition: including unnecessary variables bloats the state space; missing a variable makes the recurrence invalid
• Filling the table in the wrong order (e.g., needing dp[i+1] but iterating forward without computing it first)
• Forgetting space optimization when the problem constraints are tight (e.g., 10^5 x 10^5 grid)
• Trying to apply DP to a problem that requires greedy or graph search instead
• Not recognizing that "number of ways" problems often need modular arithmetic to avoid overflow

Anti-Patterns

Over-engineering for hypothetical scale. Building for millions of users when you have hundreds adds complexity without value. Solve today's problems first.

Ignoring the existing ecosystem. Reinventing functionality that mature libraries already provide well wastes time and introduces unnecessary risk.

Premature abstraction. Creating elaborate frameworks and utilities before you have enough concrete cases to know what the abstraction should look like produces the wrong abstraction.

Neglecting error handling at boundaries. Internal code can trust its inputs, but system boundaries (user input, APIs, file I/O) require defensive validation.

Skipping documentation for obvious code. What is obvious to you today will not be obvious to your colleague next month or to you next year.