Dynamic Programming21 sections · 916 units
Open in Course

What's Next

Preview of Broken Profile DP

Slope Trick handles continuous states with piecewise linear functions. Broken Profile DP handles 2D (two-dimensional) grid problems with complex placement constraints. In grid tiling (dominoes, tetrominoes), the state is a bitmask representing which cells are filled along a boundary.

This gives O(rows2cols)O(rows \cdot 2^{cols}) states instead of exponential in total cells. A different kind of DP improvement. With Broken Profile, you've completed the advanced DP improvement toolkit. Each technique targets a specific structure.