Dynamic Programming21 sections · 916 units
Open in Course

When Width Is Fixed

Recurrence vs DP

For fixed small width ww, broken profile DP has 2w2^w states per column. With small ww (like 33 or 44), you can often discover a formula (like an=f(an1,an2)a_n = f(a_{n-1}, a_{n-2})) by running the DP on paper. Once you have the formula, code it directly without the profile machinery.

But for variable width or complex tile shapes, you need the full DP. The profile approach is the general tool. In contests, if ww is small and fixed, try small cases by hand. If ww varies or is large (up to 1010), implement broken profile DP.