Tags
- β = solved in first try
- π = revisit
- π₯ = important
- β οΈ = solved but edge case missed
- π = solved but had to see little solution first
- π’ = solved, but less optimized
- π = out of the box
- no tag = pending/not started
How to use this tracker
For every problem, donβt jump to code. Say the four questions out loud: state? choices? combine (
+/min/max/||)? base case (i==-1easy /i==0table)? Then climb the ladder: recursion β memo β tabulation (copy the body,solveβdp) β space-opt.
8. Pattern: Dynamic Programming
8.1 Linear / 1D DP
π‘ Signal: a choice at each index;
f(i)depends on a fixed few earlier indices (i-1,i-2).
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Climbing Stairs (easy) | f(i) = f(i-1) + f(i-2). Pure Fibonacci | ||
| 2. Fibonacci Number (easy) | The base template for the whole pattern | ||
| 3. N-th Tribonacci Number (easy) | f(i) = f(i-1) + f(i-2) + f(i-3) | ||
| 4. Min Cost Climbing Stairs (easy) | f(i)=cost[i]+min(f(i-1),f(i-2)); ans min(f(n-1),f(n-2)) | ||
| 5. House Robber (medium) | π₯ | take nums[i]+f(i-2) vs skip f(i-1) | |
| 6. House Robber II (medium) | π | Circular β run linear robber twice: skip first OR skip last | |
| 7. Maximum Subarray (medium) | π₯ | Kadane: dp[i]=max(nums[i], nums[i]+dp[i-1]) | |
| 8. Delete and Earn (medium) | Bucket points by value β reduces to House Robber |
8.2 Grid / 2D DP
π‘ Signal: move through a grid (down/right); count paths or optimize path cost. State
(i, j).
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Unique Paths (medium) | π₯ | f(i,j)=f(i-1,j)+f(i,j-1); combine + | |
| 2. Unique Paths II (medium) | π | Obstacle cell β return/set 0 | |
| 3. Minimum Path Sum (medium) | π₯ | Same as Unique Paths but combine min + cell cost | |
| 4. Triangle (medium) | f(i,j)=t[i][j]+min(f(i-1,j-1), f(i-1,j)) | ||
| 5. Minimum Falling Path Sum (medium) | π | 3 parents (i-1,j-1),(i-1,j),(i-1,j+1); min over last row | |
| 6. Maximal Square (medium) | dp[i][j]=1+min(top,left,diag) if cell is β1β | ||
| 7. Dungeon Game (hard) | π | Work backwards from princess; track min health needed | |
| 8. Cherry Pickup (hard) | π | Two paths at once: dp[r1][c1][c2] |
8.3 Distinct Ways / Counting
π‘ Signal: βhow many ways to β¦β. Never optimize β sum the ways. Combine is always
+.
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Decode Ways (medium) | π₯ | 1-digit (not β0β) + 2-digit (10..26). Zeros are the traps | |
| 2. Combination Sum IV (medium) | π | Order matters β target loop OUTER. Use long long | |
| 3. Number of Dice Rolls With Target Sum (medium) | f(d,t)=Ξ£ f(d-1, t-face); mod 1e9+7 | ||
| 4. Knight Dialer (medium) | From each digit, sum moves to reachable digits; mod | ||
| 5. Count Vowels Permutation (hard) | State = last vowel; transitions per rule; mod | ||
| 6. Domino and Tromino Tiling (medium) | π | f(n)=2f(n-1)+f(n-3); derive from partial states |
8.4 0/1 Knapsack (Subsequences)
π‘ Signal: items usable at most once + a capacity/target. Take β
i-1. Combinemax/+/||.
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. 0/1 Knapsack (GfG) | π₯ | Base i==0: wt[0]<=W ? val[0] : 0 | |
| 2. Subset Sum Problem (GfG) | pick/notpick boolean; ` | ||
| 3. Partition Equal Subset Sum (medium) | π₯ | Odd total β false; else subset-sum to total/2 | |
| 4. Count Subsets with Sum (GfG) | π | Counting knapsack; zeros need care (i==-1 base is easiest) | |
| 5. Partitions with Given Difference (GfG) | s1=(sum+diff)/2; then count subsets = s1 | ||
| 6. Target Sum (medium) | π₯ | P=(total+target)/2; count subsets. i==-1 handles 0s free | |
| 7. Last Stone Weight II (medium) | π | Minimize ` | total - 2*subset |
| 8. Minimum Subset Sum Difference (GfG) | Mark reachable sums in last row, minimize diff | ||
| 9. Ones and Zeroes (medium) | π | 2D capacity: budget of m zeros and n ones |
8.5 Unbounded Knapsack
π‘ Signal: same as 0/1 but items reusable. Take β stays on
i.
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Coin Change (medium) | π₯ | Min coins; 1e8 sentinel for impossible; take stays at i | |
| 2. Coin Change II (medium) | π₯ | Count combos; 1D form β coin loop OUTER | |
| 3. Unbounded Knapsack (GfG) | Same as 0/1 but take β solve(i, ...) | ||
| 4. Rod Cutting (GfG) | π | Piece length j+1, value price[j]; reuse allowed | |
| 5. Perfect Squares (medium) | π | Coins = perfect squares β€ n; min count | |
| 6. Minimum Cost For Tickets (medium) | dp over days; 1/7/30-day passes jump ahead |
8.6 Longest Increasing Subsequence (LIS)
π‘ Signal: longest increasing/chain/divisible subsequence.
dp[i]= LIS ending ati.
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Longest Increasing Subsequence (medium) | π₯ | O(nΒ²) dp[i]; O(n log n) via tails + lower_bound | |
| 2. Largest Divisible Subset (medium) | π | Sort first, LIS with nums[i] % nums[j] == 0; track parent | |
| 3. Number of Longest Increasing Subsequence (medium) | Carry count[i] alongside len[i] | ||
| 4. Longest String Chain (medium) | Sort by length; predecessor = word with one char removed | ||
| 5. Maximum Length of Pair Chain (medium) | Sort by second; greedy or LIS-style | ||
| 6. Russian Doll Envelopes (hard) | π | Sort wβ, hβ on ties; then LIS on heights (O(n log n)) |
8.7 DP on Strings
π‘ Signal: one/two strings, compare chars at
(i, j). Use 1-based prefixes; row/col 0 = base.
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Longest Common Subsequence (medium) | π₯ | Match β 1+f(i-1,j-1); else max(f(i-1,j), f(i,j-1)) | |
| 2. Edit Distance (medium) | π₯ | No match β 1+min(insert, delete, replace) | |
| 3. Longest Palindromic Subsequence (medium) | π | LCS(s, reverse(s)) | |
| 4. Longest Palindromic Substring (medium) | π₯ | dp[i][j] = is palindrome; or expand-around-center | |
| 5. Palindromic Substrings (medium) | Count all palindromic [i..j]; expand around center | ||
| 6. Delete Operation for Two Strings (medium) | m + n - 2*LCS | ||
| 7. Distinct Subsequences (hard) | π | Match β f(i-1,j-1)+f(i-1,j); else f(i-1,j) | |
| 8. Shortest Common Supersequence (hard) | π | Length m+n-LCS; reconstruct by walking the table | |
| 9. Interleaving String (medium) | π | dp[i][j]: does s1[0..i)+s2[0..j) interleave to s3 | |
| 10. Wildcard Matching (hard) | π | * β f(i-1,j) (consume) or f(i,j-1) (empty) | |
| 11. Regular Expression Matching (hard) | π | * β zero occ f(i,j-2) or one more f(i-1,j) if match |
8.8 Decision Making / State Machine
π‘ Signal: walk an array with a carried state (holding / cooldown / transactions left).
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Best Time to Buy and Sell Stock (easy) | One transaction; track min price so far | ||
| 2. Best Time to Buy and Sell Stock II (medium) | π₯ | Unlimited; solve(i, holding); buy/sell/skip | |
| 3. Best Time β¦ with Cooldown (medium) | π | After sell jump to i+2 | |
| 4. Best Time β¦ with Transaction Fee (medium) | Subtract fee on sell | ||
| 5. Best Time β¦ III (hard) | π | At most 2 transactions β cap dimension, k=2 | |
| 6. Best Time β¦ IV (hard) | π₯ | Generalize: solve(i, holding, cap); sell β cap-1 |
8.9 Interval / Partition DP
π‘ Signal: solve on a range
[i..j], try every split pointk. Fill by increasing length.
| Question | Tags | Remember | My Solution |
|---|---|---|---|
| 1. Matrix Chain Multiplication (GfG) | π₯ | Split k in [i..j); cost arr[i-1]*arr[k]*arr[j] | |
| 2. Burst Balloons (hard) | π | k = LAST burst in (i,j); add virtual 1s at both ends | |
| 3. Minimum Cost to Cut a Stick (hard) | π | Add 0 and n as boundaries, sort cuts; interval DP | |
| 4. Palindrome Partitioning II (hard) | π | Min cuts; front partition + palindrome check | |
| 5. Partition Array for Maximum Sum (medium) | Try window sizes 1..k ending at i; use window max | ||
| 6. Minimum Cost Tree From Leaf Values (medium) | π | Interval f(i,j) = min over split of leaves | |
| 7. Guess Number Higher or Lower II (medium) | π | Minimax over pick k in [i..j]: k + max(left,right) |
Back to the guide
Patterns, ladders, and worked C++ live in the DP guide. Advanced patterns (bitmask, tree, game, probability, digit) live in Advanced DP.