Profile/Broken Profile Optimization
What you'll learn: How to drastically reduce memory in grid-based DP by tracking only the "profile" of one row or column instead of storing the entire grid state.
The Core Idea
In many grid-based dynamic programming problems (like tiling, path counting, or state propagation across a grid), a naïve approach might store the state of every cell you've processed. Profile optimization recognizes that you often only need to remember the boundary between what you've processed and what's next—typically just the current row or column.
Think of it like solving a jigsaw puzzle row by row: you don't need to remember every piece from row 1 through row 50. You only need to know how row 50 ended (its "profile") to determine how row 51 can begin.
How It Works
Instead of a DP state like dp[row][col][full_grid_state], you use dp[row][profile_of_previous_row]. The profile is a compact representation—often a bitmask—encoding just the relevant information about the boundary (e.g., which cells in the previous row are "occupied" or "available").
For example, in a grid tiling problem, the profile might be a bitmask where bit i tells you if column i of the current row has a tile extending from the previous row.
Why "Broken Profile"?
The "broken profile" variant processes cells one at a time (left-to-right, top-to-bottom) rather than entire rows, updating the profile incrementally. This can enable more complex constraints while keeping memory efficient.
Key Takeaway:
Profile optimization reduces grid DP memory from exponential in grid size to exponential only in row/column width, by tracking just the boundary state between processed and unprocessed regions.