Summary:
Help me understand this solution to the problem CSES Counting Tillings
Details:
While researching a good way to implement solution to the problem, I came across this incredibly concise solution, which solves the problem cell by cell and not the traditional column by column approach. I've been trying to understand the solution for two days now, but can't find a way. Not unexpectedly, I have no friends.
I know how the column by column approach works, I need help solving it cell by cell as in the linked solution.
Problem statement:
Find the ways to tile a n*m grid with 1*2 or 2*1 dominos.
Key Insights in the solution linked:
Although I don't understand it fully, apparently: DP[j][i][mask] is defined to be something like ways to tile full (i-1) columns, and ith column to jth row; with mask sticking out to (i+1)th column, but I'm not sure.
- Its iterating over columns.
- For each column, its iterating over each cell
- For each cell, its solving the DP for all masks, (in a weird way: I don't even understand how mask is defined for each cell)
