Dynamic Programming21 sections · 915 units
Open in Course

When to Use Broken Profile DP

Problem recognition

Use broken profile DP when you're filling a grid in order (column by column or row by row) and each step depends on which cells from the previous step remain unfilled.

Classic signals: tiling with polyominoes, placing non-overlapping shapes, or any grid DP where dp tracks "which cells in this row/column are occupied."

If the grid dimension is small (height or width ≤10\leq 10), think profiles. If both dimensions are large, broken profile DP won't fit in time or memory. But for one small dimension and one large dimension, it's perfect.