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!
Nice work on solving this problem iteratively! I lean a little bit more on the recursive side, but I will do my best to showcase both methods as I build these DP videos
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.
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.
@@paultvshowThe idea is you can create a closed form formula with this method which can be solved in O(1). The initial work of figuring out the graph, setting up the recursive formulas, deriving the closed form formula only needs to be done once.
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.
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.
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
Amazing! Thank you very much. You are brilliant teacher. Could you please explain the dp table and how did you use it in the block of code as this is the only one that confuses me. Suppoe that is , so how you could please use that to fetch values from dp as ?
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?
can't we place the the domino as vertically and horizonally both , so till the way we did dp[i-3] , after which we could arrange the next 3 spaces as 2Horizontal 1Vertcal,1V and 2H and also as all 3V , so shouln't we multiply 3*dp[i-3] ,we aren't using tromino ,and each of these 3 combination can stick to dp[i-3] to make a new way of filling dp[i]
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)
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 = 1000000007 @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) ```
@@WilliamFiset-videos thank you for the reply. I figured it out iteratively like your other video and this made perfect sense too. Thanks a bunch! These videos have been a lifesaver.
In f(i, t1,t2) The i represents the column upto which we have completely filled with tiles. We start from i = 0(empty) and go up to i = n(completely filled). If we reach i = n, then that means we've filled the entire space with a valid tile configuration. No need to check anything else. t1 and t2 represents the state of (i + 1)th column actually. When we reach at the end, this t1 and t2 must be true, otherwise we've made a mistake(we can even add an assert for the same), if any one of t3 and t4 is false, it means that we've filled past the boundary. t3 and t4 checks(that is whether i + 1 < n) ensures that we won't fill past the end boundary. On the last column, we shouldn't fill with a till with its cell beyond the boundary.
Hey! Great video. One thing is bothering me. Isn't there an error in makeState fnx? I was thinking that it should be: if !t1: state |= 1 if !t2: state |= 2?
Yeah, that looks like it should be a bug. Ultimately it doesn't matter since all the states symmetric, so the end result is the same as encoding it correctly. However both makeState functions on that slides would return a different encoding, so I see where the confusion comes from.
Complicated. I don't like it. Just write down first ~10 answers (n = 1..10) by running testcases, see the pattern and then create (recursive) sequence formula. Then just loop.
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!
Nice work on solving this problem iteratively! I lean a little bit more on the recursive side, but I will do my best to showcase both methods as I build these DP videos
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.
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.
What’s the point of using graph by the way when you can arrive at a solution much faster with DP?
@@paultvshowThe idea is you can create a closed form formula with this method which can be solved in O(1). The initial work of figuring out the graph, setting up the recursive formulas, deriving the closed form formula only needs to be done once.
I had no idea that this question was this complicated.
The way you explain is on different level...awesome man...
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.
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.
Good call out 👍
thank you for the great walk through. I could not understand the solutions until I watched this video.
This is absolute gold. Thank you for your explanation!
Leetcode daily challange 🌝
Great video! A video about Treaps would be awesome!
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
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
Amazing! Thank you very much. You are brilliant teacher. Could you please explain the dp table and how did you use it in the block of code as this is the only one that confuses me. Suppoe that is , so how you could please use that to fetch values from dp as ?
Thanks for excellent pictorial explaination
Great explanation, thank you so much!
Recursive is much easier to grasp as it imo in most cases better reflects the 'natual' way of problem decomposition.
Great solution!!
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?
can't we place the the domino as vertically and horizonally both , so till the way we did dp[i-3] , after which we could arrange the next 3 spaces as 2Horizontal 1Vertcal,1V and 2H and also as all 3V , so shouln't we multiply 3*dp[i-3] ,we aren't using tromino ,and each of these 3 combination can stick to dp[i-3] to make a new way of filling dp[i]
@@mickyman753 I am having the same confusion, I'll let you know if I figure anything out
Golden content
Very helpful, thanks man.
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)
This is great! Thanks
This was sooooo beautiful
great video! it was so helpful :)
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 = 1000000007
@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)
```
why are we taking 4 columns in dp array? one for each state?
Thank you so much !!!!
Awesome
So, for 2 columns (4 cells) there are 9 valid states.
This confused me a lot. So there is no iterative solution like previous problem for 3xN board? Why does that same concenpt not apply here?
The same concept does apply, I'm simply displaying another way to solve the problem by using recursion :)
@@WilliamFiset-videos thank you for the reply. I figured it out iteratively like your other video and this made perfect sense too. Thanks a bunch! These videos have been a lifesaver.
May I know the time complexity of this solution please 🥺
O(n)
In the base case, shouldnt we be writing, if(i+1 == n && !t1 && !t2) {return 1;}
In f(i, t1,t2)
The i represents the column upto which we have completely filled with tiles.
We start from i = 0(empty) and go up to i = n(completely filled). If we reach i = n, then that means we've filled the entire space with a valid tile configuration. No need to check anything else.
t1 and t2 represents the state of (i + 1)th column actually. When we reach at the end, this t1 and t2 must be true, otherwise we've made a mistake(we can even add an assert for the same), if any one of t3 and t4 is false, it means that we've filled past the boundary.
t3 and t4 checks(that is whether i + 1 < n) ensures that we won't fill past the end boundary. On the last column, we shouldn't fill with a till with its cell beyond the boundary.
Hey! Great video.
One thing is bothering me. Isn't there an error in makeState fnx?
I was thinking that it should be:
if !t1: state |= 1
if !t2: state |= 2?
Yeah, that looks like it should be a bug. Ultimately it doesn't matter since all the states symmetric, so the end result is the same as encoding it correctly. However both makeState functions on that slides would return a different encoding, so I see where the confusion comes from.
Great catch! Even I was confused regarding this.
Complicated. I don't like it. Just write down first ~10 answers (n = 1..10) by running testcases, see the pattern and then create (recursive) sequence formula. Then just loop.
My Solution with O(n) time and O(1) space complexity :-
class Solution {
public:
int numTilings(int n) {
if(n==1)
return 1;
vector buffer(5, 0);
buffer[0]=0;
buffer[1]=1;
buffer[2]=1;
buffer[3]=2;
for(int i=4; i
Did run into this:
Tilings of 2 × n boards with dominos and
L-shaped trominos
dresden.academic.wlu.edu/files/2021/01/TwoByNWeb.pdf