Dynamic Programming

Dynamic programming solves problems with two properties: optimal substructure (the optimal solution contains optimal subsolutions) and overlapping subproblems (the same subproblem is solved multiple times in naïve recursion). The three-step approach: (1) Define the state clearly; (2) Write the recurrence relation; (3) Determine base cases and evaluation order. Memoization and tabulation are equivalent in theory but tabulation is often more space-efficient. The hardest part is always defining the RIGHT state. Understanding Dynamic Programming DP solves problems by breaking them into overlapping subproblems. If a problem has optimal substructure (optimal solution uses optimal solutions to subproblems) and overlapping subproblems (same subproblem solved multiple times), use DP. Two approaches: Top-down (memoization): recursive with cache — easier to write, natural for tree-shaped subproblems Bottom-up (tabulation): iterative with table — often faster, easier to optimize space The 5-step framework: Define state: what information do you need to solve the subproblem? Define recurrence: how does the current state relate to smaller states? Base cases: what are the smallest subproblems with known answers? Compute order: bottom-up — solve smaller problems first Extract answer: where in the table is the final answer? Common patterns: 1D DP: Fibonacci, climbing stairs, house robber 2D DP: grid paths, longest common subsequence, edit distance Knapsack: subset sum, coin change, partition equal subset Interval DP: matrix chain multiplication, burst balloons Interview tip: Start with brute force recursion, add memoization, then convert to bottom-up if needed. Dynamic Programming DP solves problems by breaking them into overlapping subproblems and storing results to avoid recomputation. The Framework Define the state: = answer for subproblem of size i Find the recurrence: Set base cases: Determine iteration order Classic Problems Climbing Stairs (1D DP): Longest Common Subsequence (2D DP): 0/1 Knapsack: Key Problems #70 Climbing Stairs, #198 House Robber, #322 Coin Change #1143 LCS, #300 LIS, #72 Edit Distance Interview Tip "For DP, I always start by defining the state clearly. If I can express the answer for dp[i] in terms of smaller subproblems, it's DP." Java Implementation: