1D Dynamic Programming — Master Recap & Cheatsheet
Sanjeev SharmaAdvertisement
1D DP Master Cheatsheet
Pattern Reference
| Pattern | Transition | Example |
|---|---|---|
| Fibonacci | dp[i] = dp[i-1] + dp[i-2] | Climbing Stairs |
| House Robber | dp[i] = max(dp[i-1], dp[i-2]+nums[i]) | House Robber |
| Kadane | curr = max(x, curr+x) | Max Subarray |
| Unbounded Knapsack | dp[i] += dp[i-c] (fwd) | Coin Change II |
| 0/1 Knapsack | dp[j] = max/or dp[j-w] (bwd) | Partition Equal Sum |
| LIS O(n log n) | bisect_left + extend/replace | LIS |
| Decode Ways | dp[i] += dp[i-1] + dp[i-2] (conditional) | Decode Ways |
| Jump Game | reach = max(reach, i+nums[i]) | Jump Game |
Key Insights
Knapsack Loop Direction:
- 0/1 (each item once): loop amounts backwards →
for j in range(target, w-1, -1) - Unbounded (item reusable): loop amounts forwards →
for j in range(w, target+1) - Count combinations: coins outer, amounts inner
- Count permutations: amounts outer, coins inner
LIS Patience Sort:
tails[i]= smallest tail of length-(i+1) subsequencesbisect_left= position where new element goes- Length of tails = LIS length
Kadane Extensions:
- Product: track min AND max (negatives can flip)
- Circular: max(normal, total - min_subarray)
Complexity Summary
| Algorithm | Time | Space |
|---|---|---|
| Fibonacci-type | O(n) | O(1) |
| Kadane | O(n) | O(1) |
| Coin Change | O(n*amount) | O(amount) |
| 0/1 Knapsack | O(n*W) | O(W) |
| LIS (n²) | O(n²) | O(n) |
| LIS (patience) | O(n log n) | O(n) |
| Word Break | O(n² * m) | O(n) |
Problem Index
Fibonacci: Climbing Stairs (01), Min Cost (02), Tribonacci (04)
House Robber: House Robber (03), Circular (04), Delete & Earn (05)
Kadane: Max Subarray (06), Max Product (07)
Unbounded Knapsack: Coin Change (08), Coin Change II (09), Perfect Squares (10)
Greedy: Jump Game (11), Jump Game II (12)
Counting DP: Decode Ways (13), Word Break (14), Target Sum (20)
LIS: LIS (15), Russian Doll Envelopes (16)
Palindrome: Palindromic Substrings (17), Longest Palindromic Subsequence (18)
0/1 Knapsack: Partition Equal Sum (19), Target Sum (20)
Advertisement
