patternDSA/Dynamic Programming
Foundation → Pattern 01

Dynamic Programming

The most powerful algorithmic technique in computer science. Transforms exponential brute-force into elegant polynomial solutions.

Frequency:★★★★★
·~60 min·Advanced·3 problems
The Core Shock

Fibonacci(50) — 1 quadrillion calls vs 49 calls

Naive Recursion
1,125,899,906,842,624
calls for fib(50)
O(2ⁿ)
With Memoization
49
calls for fib(50)
O(n)

The insight: fib(3) appears in the recursion tree dozens of times. Each time, we recompute it from scratch. DP says: compute it once, store it, look it up instantly.

The Two Necessary Conditions

Both must hold for DP to apply. Learn to test for them instantly.

Overlapping Subproblems

The same smaller problem appears multiple times when solving the larger problem. fib(3) in fib(10) is computed over and over.

Test: Ask: 'Does my recursion recompute the same subproblem multiple times?' If yes → overlapping.
Optimal Substructure

The optimal solution to the large problem is built from optimal solutions to its subproblems. Shortest A→C = shortest(A→B) + shortest(B→C).

Test: Ask: 'Can I express best(n) in terms of best(smaller n)?' If yes → optimal substructure.

The 3-Step DP Framework

The thinking process every DP expert uses. Internalize it.

01
Define the State

What does dp[i] (or dp[i][j]) represent? Be precise. Vague state = wrong recurrence.

dp[i] = "max profit robbing houses 0..i"
If you cannot explain dp[i] in one clear sentence, you are not ready to write the recurrence.
02
Write the Recurrence

How does dp[i] depend on smaller subproblems? What choices exist at each step?

dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Think: what CHOICES do I have at position i? What is the optimal outcome of each?
03
Handle Base Cases

What are the smallest valid states? These are the seeds your recurrence grows from.

dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
Missing base cases is the number one DP bug. Identify them before writing the loop.

4 DP Variants — Know Them All

Every DP problem fits one of these categories.

1D Linear

dp[i] depends on dp[i-1], dp[i-2]. Single array, small lookback.

FibonacciHouse RobberClimbing StairsDecode Ways
Sequential decisions, small lookback
1D Jump (Unbounded)

dp[i] considers ALL previous states — not just adjacent ones.

Coin ChangeWord BreakLIS
Choose from any prior state
2D (String / Grid)

dp[i][j] has two dimensions: two strings, two sequences, or a grid.

LCSEdit DistanceUnique PathsKnapsack
Two varying parameters
Interval DP

dp[i][j] = answer for subarray [i..j]. Try every split point k.

Burst BalloonsMatrix ChainPalindrome Partition
Subproblem over a range

Pattern Recognition

30-second diagnosis: is this DP?

Use DP When
"How many ways..." with overlapping structure
"Maximum / minimum" with choices
"Can we achieve exactly X?"
Brute force is O(2ⁿ) or O(n!)
Recursion recomputes same subproblems
"Optimal sequence / ordering"
Do NOT Use DP When
Greedy choice always works (interval scheduling)
Subproblems do not overlap (Merge Sort)
Simple sorted scan gives the answer
No decisions at each step — just compute
Problem is trivially O(n)