Dynamic Programming21 sections · 916 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.