TRT
Sign in

Advanced · Module 21 · Lesson 4 of 4

DP State Patterns: 1D/2D/Knapsack vs. Interval DP, Tree DP, and Bitmask DP

Design minimal DP states and transition order across all 8 canonical DP families: 1D/2D Grid, Subsequence, 0/1 & Unbounded Knapsack, Interval DP (len 1..N), Tree DP, and Bitmask DP.

Pro — members onlyAbout 18 minutes

By the end you can

  • Map problem constraints and decision structures to the 8 canonical DP state families
  • Order loops correctly for 0/1 Knapsack (capacities high-to-low) vs Unbounded Knapsack (capacities low-to-high) and Interval DP (by length len = 1..n)
  • Formulate Bitmask DP (dp[mask][u]) for N <= 20 ordering/TSP problems and Tree DP for subtree aggregations

Builds on One-dimensional problems, Grids and strings, Knapsack and subsets, Bit Manipulation Tricks and Submask Enumeration.

01 · A question first

In 1D Space-Optimized Knapsack, reversing a single inner loop from `w = W down to weight` into `w = weight up to W` silently changes the problem from 0/1 Knapsack (each item once) to Unbounded Knapsack (infinite copies of each item)! Why does loop direction control item reuse?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Intuitive Explanation & Real-World Analogy
  • Core Concepts & Visual Walkthrough
  • Pseudocode
  • Multi-Language Implementations (C++, Java, Python)
  • Time & Auxiliary Space Complexity Derivation
  • Edge Cases & Common Beginner Mistakes
  • Alternative Approaches (Brute Force vs. Optimal)
  • Pattern Recognition Guide & Three-Stage Practice Plan
See plansAlready a member? Sign in

03 · Practice

Practice · hard · LeetCodeBurst balloonsMaximize the coins from bursting balloons with an interval DP over which balloon in each range bursts last.Practice · medium · LeetCodeLongest palindromic subsequenceFind the longest subsequence of a string that reads the same backward, with an interval DP on the string's two ends.Practice · medium · LeetCodeHouse robber IIRob houses arranged in a circle by solving the straight-line problem twice, once without the first house and once without the last.Practice · medium · LeetCodePartition equal subset sumDecide whether an array can be split into two equal-sum halves, as a subset-sum table with a downward loop.

Asked in interviews

Something wrong with this lesson? Report a problem