Tiling Dominoes and Trominoes (Leetcode 790) | Dynamic Programming

Explanation video on how to tile a 2xN grid with dominoes and L shaped trominoes.

Leetcode problem:

Source code:

Algorithms repo:

Previous video on tiling dominoes:

Video slides:

Website:

0:00 Intro
0:31 Tiling dominoes and trominos problem statement and examples
2:02 Problem hints
3:15 Problem analysis
6:45 State transition
8:45 Pseudocode
===============================================================================
Developer tools I used in the creation/testing of the content in these videos:

2) Kite, a free AI-powered coding assistant that provides smart code completions while typing:
===============================================================================

[janmejaysingh]

I had no idea that this question was this complicated.

[arunasimas]

I love the solution. Very clear. Seems its easier to come up with this one than inventing this formula quickly:
dp[n] = 2 * dp[n-1] + dp[n-3]

[capitols]

Hey! I was able to solve this problem the iterative way after watching your previous video. It took me a while to work out the recurrence relation (I'm a DP beginner). The key for me was knowing that maintaining each possible board state is necessary. I am slowly wrapping my head around 2D memo tables.
For whatever reason it's really challenging for me to produce a recursive + memo solution. I can mostly manage to get a brute force solution and then sometimes a bottom up iterative. To answer your question at the end: it'd be really helpful to see both top-down and bottom-up solutions to each problem. If that ask is too large, the middle ground where you're solving similar problems with different approaches works.
These videos are a great resource, thanks for making them!

[ramumaha]

The method of explanation is very intuitive.Gives the viewer step by step analysis of how to approach such problems.Thanks for this very detailed video.

[nikhildinesan]

The way you explain is on different level...awesome man...

[horndude]

These types of problems can also be solved with a directed graph where the nodes represent the right edge state and the weights are how many squares are in the tile (it'd be easier to draw than write with text). In any case here's the graph.

Set up graph:
[00] ->3 [10] (place rotated 'L')
[00] ->3 [01] (place 'L')
[00] ->2 [02] (place horizontal 2x1)
[00] ->2 [00] (place vertical 2x1)

[10] ->3 [00] (place 'L')
[10] ->2 [01] (place horizontal 2x1)

[01] ->3 [00] (place 'L')
[01] ->2 [10] (place horizontal 2x1)

[02] ->2 [00] (place horizontal 2x1)

After that it can be converted to a system of recursive equations which counts the number of ways to traverse the graph and end in a certain node. We're starting with a blank board so a_{0} is 1 for one way to tile a blank board. All other initial states are zero.

a_{n} = b_{n-3} + c_{n-3} + d_{n-2} + a_{n-2}
a_{0} = 1
b_{n} = a_{n-3} + c_{n-2}
c_{n} = a_{n-3} + b_{n-2}
d_{n} = a_{n-2}

You can get answers with this, but with some simplification we can get a better equation (exercise for the reader).

a_{n} = 2*a_{n-1} + a_{n-3}
a_{0} = 1
a_{1} = 1
a_{2} = 2

This of course could be taken further (like with the fibonacci series), but with this you can calculate very large values quickly and simply.

[lazylama]

For those of you that want to turn this very nice solution into Java code, be warned: the count value can cause integer overflow errors. Because in this solution, only add the end do we do count % mod. But with n=29 and up, the count value will get to big before we reach that line with the modulo division. Therefore you should already use the mod division before reaching that line.

[عزالدينبنعبدالرحمن]

That was helpful! I checked some solutions on LC, they were using some formula which I spent a big amount of time trying to figure it out and I couldn't even understand their formula, but your solution (definitely bigger in length) was much simpler to understand.

[FinLogan]

Thank you for the video! Small error at 1:58, the first row has the same element at positions 2 and 4, I think you meant to have the shape from 1 but put the vertical bar on the opposite side

[mashab]

thank you for the great walk through. I could not understand the solutions until I watched this video.

[noctua]

This is absolute gold. Thank you for your explanation!

[darshika]

I went through a lot of video solutions for this problem, and this one is by far the most illustrative and easy to understand solution

[andreytamelo]

Recursive is much easier to grasp as it imo in most cases better reflects the 'natual' way of problem decomposition.

[algoseekee]

That's good. I could derive a formula 2 * dp[i - 1] + dp[i - 3] using your explanations in the middle! For each column, we could end up on state 1 & state 2 for the previous column which means we could combine them symmetrically and it gives 2 * dp[i - 1]. Also if take 2 steps back, on dp[i - 3], we simply can move to the current column without trominoes (which are already covered) using dominoes only which means it's the same amount of ways as for dp[i - 3]. However, the last part is not 100% clear to me, could you validate my logic, please?

[fernandomorato]

Great video! A video about Treaps would be awesome!

[AlejandroRuiz-pdci]

Great explanation, thank you so much!

[tarunpatel]

Thanks for excellent pictorial explaination

[skrzyp]

I rewrote it to Python and merged a few cases to make it shorter. It's possible to further simplify this code, i.e. merge state 1 & 2:
```python3
class Solution:
def numTilings(self, n: int) -> int:
MOD =
@cache
def dp(i, state):
if i == n:
return 1
nxt_state = i + 1 < n
count = 0
if state == 3 and nxt_state: # XX | # X
count += 2 * dp(i + 1, 2) # X | # XX

if state in [1, 2, 3] and nxt_state: # XX | # #X | # XX
count += dp(i + 1, 0) # #X | # XX | # XX

if state in [0, 3]: # X | # #
count += dp(i + 1, 3) # X | # #

if state == 1 and nxt_state: # XX
count += dp(i + 1, 2) # #

if state == 2 and nxt_state: # #
count += dp(i + 1, 1) # XX
return count % MOD
return dp(0, 3)
```

[keerthis]

why are we taking 4 columns in dp array? one for each state?

[sameerprajapati]

It was great how you explained all the states and how we could compute the current states from previous states, but as soon as I saw the long and messy code, I lost my interest completely. You could have used a simple code with an array of length 4 containing all possible states and computing the values based on the last array(state)