I know there are a number of different tiling problems and some of them have been discussed here: Number of ways of tiling a 3*N board with 2*1 dominoes problem Domino and Tromino Combined Tiling DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?. My domain has different requirements which are as below: https://www.codingame.com/ide/puzzle/3n-tiling
Height will be 3, tile sizes are: 2x2, 3x1, 1x3
there are possible choices for 3x6:
┌─────┬─────┐ ┌───┬───┬───┐ ┌─────┬─────┐ ┌─┬─┬─────┬─┐
├─────┼─────┤ │ │ │ │ ├───┬─┴─┬───┤ │ │ ├─────┤ │
├─────┼─────┤ ├───┴─┬─┴───┤ │ │ │ │ │ │ ├─────┤ │
└─────┴─────┘ └─────┴─────┘ └───┴───┴───┘ └─┴─┴─────┴─┘
┌─┬─────┬─┬─┐ ┌─┬─┬─┬─────┐ ┌─────┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┐
│ ├─────┤ │ │ │ │ │ ├─────┤ ├─────┤ │ │ │ │ │ │ │ │ │ │
│ ├─────┤ │ │ │ │ │ ├─────┤ ├─────┤ │ │ │ │ │ │ │ │ │ │
└─┴─────┴─┴─┘ └─┴─┴─┴─────┘ └─────┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┘
(illustration copied from Codingame problem section).
I have come up with the following DP relation:
dp[i] = (dp[i-1] + (i >= 3 ? dp[i-3] : 0) + (i >= 6 ? dp[i-6] * 2 : 0))
dp[i-1]
means at each state, you can add a 1x3 (illustration below) to previous state to get to the current state.
┌─┐
│ │
│ │
└─┘
dp[i-3]
means if your width is at least 3, you can stack up three 3x1 vertically to 3 states ago (width - 3) to get to current state.
┌─────┐
├─────┤
├─────┤
└─────┘
dp[i-6]
means when my width is greater than or equal to 6, I can add three 2x2 squares horizontally next to each other, then put two 3x1 rectangles on top of them to 6 states ago(width - 6), in two ways, to get to current state).
┌───┬───┬───┐ ┌─────┬─────┐
│ │ │ │ ├───┬─┴─┬───┤
├───┴─┬─┴───┤ │ │ │ │
└─────┴─────┘ └───┴───┴───┘
But looks like I'm missing something, my solution for 3x12 returns 124, while it should be 154. Any help is appreciated.
Edit:
After a lot of thoughts and getting some ideas from answers, I came up with this solutions (Image represents a top down DP approach)
Basically, based on the image,
- To get to 1xN state, we can take 1 time, 1x3 and so dpHeight1[n] = dpHeight1[n-3]
- To get to 2xN state, we can either take 1 time 2x2 so dpHeight2[n] = dpHeight2[n-2] or we can take 2 times 1x3: dpHeight2[n] += dpHeight2[n-3]
- to get to 3xN, we can either take 1 time 3x1, so dpHeight3[n] = dpHeight3[n-1] or we can take 3 time 1x3, dpHeight3[n] += dpHeight3[n-3] or take 1 time 2x2 and 1 time 1x3, exception here is we can take 1x3 first or after we take 2x2, but they both have same count, so: dpHeight3[n] += (dpHeight1[n-3] * dpHeight2[n-2] * 2)
And this the code:
dpHeight1[0] = 1//height = 1
dpHeight2[0] = 1//height = 2
dpHeight3[0] = 1//height = 3
for (int width=1; width <= n; width++) {
//take out one 1x3
dpHeight3[width] = (dpHeight3[width-1])%mod
if width >= 2 {
dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-2])%mod
}
if width >= 3 {
//put 1 time 3x1
dpHeight1[width] = (dpHeight1[width] + dpHeight1[width-3])%mod
//put 2 vertically stacked 3x1
dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-3])%mod
//take out 3 vertically stacked times 3x1
dpHeight3[width] = (dpHeight3[width] + dpHeight3[width-3])%mod
//take out 1 time 2x2 and put it on top of 1 time 3x1
// or take out 1 time 3x1 and put it on top of 1 time 2x2
dpHeight3[width] = (dpHeight3[width] + 2 * (dpHeight2[width-2] * dpHeight1[width-3]))%mod
}
}
But still not getting the result.
dpHeight3[n] += (dpHeight1[n-3] * dpHeight2[n-2] * 2)
This is wrong. There are more arrangement. $\endgroup$ – John L. Apr 10 '20 at 2:20