3xN tiling problem with blocks of size 3x1 or 2x2 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 &gt;= 3 ? dp[i-3] : 0) + (i &gt;= 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 &lt;= n; width++) {
    //take out one 1x3
    dpHeight3[width] = (dpHeight3[width-1])%mod

    if width &gt;= 2 {
        dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-2])%mod
    }

    if width &gt;= 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.
Here is a systematic way to approach it.  I suggest you define three values:

$A_0(n)$ is the number of ways to tile a $3 \times n$ region.

$A_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered.

$A_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of it already covered.

Then you should be able to express each $A_i(n)$ in terms of $A_j(m)$ for $m &lt; n$.  This gives you a mutual recurrence relation for these three values.  It is easy to construct these recurrent relations based on a case analysis of how the leftmost column is covered.

You can then compute these using dynamic programming, in order of increasing $m$.  Or, you can substitute into each other and get a single recurrence relation for $A_0(n)$ in terms of $A_0(m)$ for $m&lt;n$, if you prefer.



Regarding your solution:

Yeah, you're missing something.  For instance, a solution could start

┌───┬───┬─────┐
│   │   ├─────┤
├───┴─┬─┴───┬─┴ 
└─────┴─────┴──


and continue from there; that won't be counted in your case analysis.