Om's Brain

0. Questions

9 min read

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==-1 easy / i==0 table)? 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).

QuestionTagsRememberMy 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).

QuestionTagsRememberMy 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 +.

QuestionTagsRememberMy 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. Combine max / + / ||.

QuestionTagsRememberMy 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.

QuestionTagsRememberMy 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 at i.

QuestionTagsRememberMy 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.

QuestionTagsRememberMy 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).

QuestionTagsRememberMy 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 point k. Fill by increasing length.

QuestionTagsRememberMy 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.

9. Pattern: Advanced Dynamic Programming

πŸ’‘ See Advanced DP for the templates. Use these only once the core nine patterns above are automatic.

9.1 Bitmask DP

πŸ’‘ Signal: n is tiny (≀ ~20); state = β€œwhich elements have I used/visited” encoded as bits.

QuestionTagsRememberMy Solution
1. Partition to K Equal Sum Subsets (medium)πŸ”₯dp[mask] = fill of current bucket; %target auto-closes it
2. Matchsticks to Square (medium)Special case of Partition to K Equal Sum Subsets, k = 4
3. Shortest Path Visiting All Nodes (hard)πŸ’€BFS over (node, mask) states; mask = nodes visited
4. Smallest Sufficient Team (hard)πŸ’€dp[skillMask] = smallest team covering those skills
5. Maximum Students Taking Exam (hard)πŸ’€Row-by-row bitmask; check no-cheat with left/right/diag masks
6. Minimum Cost to Connect Two Groups of Points (medium)πŸ“dp[i][mask] = cost pairing group1[0..i) with group2 subset mask
7. Traveling Salesman (TSP) (GfG)πŸ”₯dp[mask][i] = min cost visiting mask, ending at i

9.2 Tree DP

πŸ’‘ Signal: answer at a node is built from its children’s answers. Post-order + return a tuple.

QuestionTagsRememberMy Solution
1. House Robber III (medium)πŸ”₯Return {robThis, skipThis}; robThis uses children’s skip only
2. Binary Tree Maximum Path Sum (hard)πŸ”₯Return best downward path; combine both sides only at the root
3. Diameter of Binary Tree (easy)Track height per node; diameter = leftHeight + rightHeight
4. Binary Tree Cameras (hard)πŸ’€3 states per node: covered/has-camera/not-covered
5. Unique Binary Search Trees II (medium)πŸ“For each root, combine all left-subtree Γ— right-subtree pairs
6. Longest Path With Different Adjacent Characters (hard)πŸ“Same as diameter, but only count children with different char
7. Distribute Coins in Binary Tree (medium)πŸ“Post-order excess/deficit; moves += abs(excess)

9.3 Game / Minimax DP

πŸ’‘ Signal: two players alternate optimally. solve(state) = best score DIFFERENCE (me βˆ’ opponent).

QuestionTagsRememberMy Solution
1. Predict the Winner (medium)πŸ“max(nums[i]-f(i+1,j), nums[j]-f(i,j-1)); INT_MIN sentinel
2. Stone Game (medium)πŸ”₯Same recurrence as Predict the Winner, even-length array
3. Stone Game II (medium)πŸ“solve(i, M): pick x in [1..2M] piles; opponent gets M=max(M,x)
4. Stone Game III (hard)πŸ“Pick 1-3 from front; same diff trick, ternary choice
5. Nim Game (easy)Losing iff n % 4 == 0 β€” math shortcut, no table needed
6. Can I Win (medium)πŸ’€Bitmask of used numbers + minimax; memoize on mask

9.4 Probability / Expected Value DP

πŸ’‘ Signal: β€œprobability that…” / β€œexpected number of…”. Combine = weighted sum over branches.

QuestionTagsRememberMy Solution
1. Knight Probability in Chessboard (medium)πŸ“Sum of solve(k-1, next) / 8 over all 8 knight moves
2. New 21 Game (medium)πŸ’€dp[i] = prob of stopping at score i; sliding window sum of next W
3. Soup Servings (medium)πŸ“solve(a,b) avg of 4 equally likely serve operations; cap N~180
4. Random Walk / Frog’s Position After T Seconds (hard)πŸ“DFS with probability multiplied along the path

9.5 Digit DP

πŸ’‘ Signal: count numbers in [L, R] (huge range) with a digit property. State = (pos, tight, ...).

QuestionTagsRememberMy Solution
1. Numbers At Most N Given Digit Set (hard)πŸ”₯Count shorter lengths directly + digit DP for exact length
2. Non-negative Integers without Consecutive Ones (hard)πŸ“State tracks β€œwas last bit 1”; memoize only when !tight
3. Count of Integers (hard)πŸ’€Digit DP tracking running digit-sum in state
4. Digit Count in Range (GfG)count(R) - count(L-1); classic template application

9.6 Broken-Profile / Bitmask-on-Grid DP

πŸ’‘ Signal: tile/fill a grid, cols ≀ ~14. State = frontier bitmask processed column by column.

QuestionTagsRememberMy Solution
1. Domino and Tromino Tiling β€” 2Γ—N (GfG)πŸ“Classic 2-column broken profile; recognize before coding
2. Painting a Grid With Three Different Colors (hard)πŸ’€Column-by-column color mask; adjacent-column compatibility
3. Number of Ways to Wear Different Hats to Each Other (hard)πŸ’€Bitmask over people (small n), iterate hats outer

9.7 DP Optimizations

πŸ’‘ Signal: correct DP is too slow; speed up the TRANSITION, not the state.

QuestionTagsRememberMy Solution
1. Jump Game VI (medium)πŸ”₯dp[i] = nums[i] + max(dp[i-k..i-1]); monotonic deque for the max
2. Constrained Subsequence Sum (hard)πŸ“Same monotonic-deque-over-window shape as Jump Game VI
3. Sliding Window Maximum (hard)The monotonic deque itself β€” learn this before the DP variants
4. Super Egg Drop (hard)πŸ’€Reframe state to (moves, eggs) β†’ answer = # eggs broken; O(n log n)
5. Ugly Number III (medium)Binary search + inclusion-exclusion, not really DP β€” good contrast

Mindmap

Graph View

Backlinks