Dynamic Programming
Break complex problems into overlapping subproblems — the ultimate interview topic
0/120 solved
1D Linear DP
Single array DP where state depends on previous elements
Approach
Define dp[i] as the answer for the first i elements. Build from dp[0] using a recurrence that depends on previous states.
How to Recognize
Problem can be solved by building the answer from left to right, one element at a time
State at index i depends only on states at i-1, i-2, or a small fixed lookback
Classic keywords: 'climbing stairs', 'house robber', 'decode ways', 'tiling'
You need to make a binary choice at each step: include or exclude the current element
Brute force would be exponential (try all subsets), hinting at overlapping subproblems
The problem has 'optimal substructure' — optimal solution contains optimal sub-solutions
Fibonacci-style recurrence: each state is a combination of a fixed number of previous states
Constraints suggest O(n) or O(n·k) solution — linear scan with DP transitions
Pro Tips
Often space-optimizable from O(n) to O(1) by keeping only the last 2-3 values in variables
Check if greedy works first — DP might be overkill for problems with greedy-optimal structure
For circular variants (House Robber II), run DP twice: once excluding first element, once excluding last
When the recurrence involves choices (take/skip), think of it as a 'decision at each index' problem
Draw the recursion tree first to identify overlapping subproblems — memoize top-down, then convert to bottom-up
Watch for off-by-one errors in base cases: dp[0] and dp[1] often need special handling
8
Total
3
Easy
5
Medium
0
Hard
Time
O(n)
Space
O(1) optimized