Common problems solved using DP on broken profile include:
Problem description. Given a grid of size \(N \times M\). Find number of ways to fill the grid with figures of size \(2 \times 1\) (no cell should be left unfilled, and figures should not overlap each other).
Let the DP state be: \(dp[i, mask]\), where \(i = 1, \ldots N\) and \(mask = 0, \ldots 2^M - 1\).
\(i\) represents number of rows in the current grid, and \(mask\) is the state of last row of current grid. If \(j\)-th bit of \(mask\) is \(0\) then the corresponding cell is filled, otherwise it is unfilled.
Clearly, the answer to the problem will be \(dp[N, 0]\).
We will be building the DP state by iterating over each \(i = 1, \cdots N\) and each \(mask = 0, \ldots 2^M - 1\), and for each \(mask\) we will be only transitioning forward, that is, we will be adding figures to the current grid.
int n, m;
vector < vector<long long> > dp;
void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)
{
if (x == n)
return;
if (y >= m)
dp[x+1][next_mask] += dp[x][mask];
else
{
int my_mask = 1 << y;
if (mask & my_mask)
calc (x, y+1, mask, next_mask);
else
{
calc (x, y+1, mask, next_mask | my_mask);
if (y+1 < m && ! (mask & my_mask) && ! (mask & (my_mask << 1)))
calc (x, y+2, mask, next_mask);
}
}
}
int main()
{
cin >> n >> m;
dp.resize (n+1, vector<long long> (1<<m));
dp[0][0] = 1;
for (int x=0; x<n; ++x)
for (int mask=0; mask<(1<<m); ++mask)
calc (x, 0, mask, 0);
cout << dp[n][0];
}