§ CSES: Counting Towers
- Link to problem I found the problem interesting, as I found the DP states un-obvious.
- I eventually performed a DP on the the number of possible towers in y-axis
[0, h) where we keep track of whether the last layer has a
2x1 tile or two
- Importantly, this means that the decision of "closing" a section to create a new section is left to the next DP state.
- This is weirdly reminisecent of some kind of topological phenomena, where we use intervals of the form
[l, l+1) to cover a space.
- It seems to help me to look at this kind of DP as first creating the combinatorial objects, and then switching it over to counting the number of such objects created.