menu_bookGyanByte
Practice SetLesson 241 min read

Advanced DP — Practice Problems

November 05, 2026

// How to use this set

Drill the three hard DP shapes: medium (Partition to K Equal Sum Subsets, House Robber III, Stone Game, Partition Array for Maximum Sum) → hard (Shortest Path Visiting All Nodes, Burst Balloons, Minimum Cost to Cut a Stick, Count Vowels Permutation, Student Attendance Record II, Maximum Profit in Job Scheduling). For each, first name the state — subset? range? subtree? — then write the recurrence. Every solution below was run and tested.

Ten problems that drill bitmask, interval, and tree DP from Lesson 24. The work is identifying the state shape; once you know it’s a bitmask (or an interval, or a tree), the recurrence is a template. Each solution here was actually run and tested.

How to practise. Read the constraints first. n ≤ 20? It’s probably bitmask. A contiguous range where order matters? Interval. A tree? Tree DP. Decide the state out loud, write the recurrence, then check. Advanced DP rewards pattern recognition over cleverness.

The 10 problems

  1. 1Partition to K Equal Sum Subsets (LeetCode 698)MediumSplit numbers into k groups of equal sum: memoise on (used-mask, room left in the current bucket).arrow_forward
  2. 2House Robber III (LeetCode 337)MediumMax loot from a binary tree with no two adjacent nodes robbed: each node returns (rob it, skip it).arrow_forward
  3. 3Stone Game (LeetCode 877)MediumTwo players take piles from either end: dp(i, j) is the best score lead the mover can force on piles[i..j].arrow_forward
  4. 4Partition Array for Maximum Sum (LeetCode 1043)MediumCut an array into blocks of length ≤ k, each becomes its max: dp over prefixes, trying every last block.arrow_forward
  5. 5Shortest Path Visiting All Nodes (LeetCode 847)HardFewest edges to visit every node, revisits allowed: BFS where the state is (current node, set visited).arrow_forward
  6. 6Burst Balloons (LeetCode 312)HardMax coins from bursting balloons: pick which balloon in a range bursts last, so its neighbours are fixed.arrow_forward
  7. 7Minimum Cost to Cut a Stick (LeetCode 1547)HardOrder cuts on a stick to minimise total cost: interval DP over cut positions, splitting on the first cut.arrow_forward
  8. 8Count Vowels Permutation (LeetCode 1220)HardCount length-n vowel strings obeying follow rules: track how many strings end in each vowel and roll forward.arrow_forward
  9. 9Student Attendance Record II (LeetCode 552)HardCount length-n P/A/L records with < 2 absences and no 3 lates in a row: DP on (day, absences, trailing lates).arrow_forward
  10. 10Maximum Profit in Job Scheduling (LeetCode 1235)HardPick non-overlapping jobs for max profit: sort by end, binary-search the last compatible job, extend its best.arrow_forward
coding-interviewdynamic-programmingleetcodepythonpractice
arrow_back Back to the lessonAdvanced Dynamic ProgrammingNext lesson arrow_forwardString Algorithms: KMP & Rabin-Karp