[Music] [Music] hello and welcome back this is William today we're tackling another tiling problem which involves tiling dominoes and drama notes on a board this problem is interesting because we're not only dealing with one type of block but two types of blocks the problem we're trying to tackle asks in how many ways can you tile a 2 by n rectangle grid with 2 by 1 dominoes and l-shaped Trauma knows where n is an integer between 1 and 1000 return the answer modulo 10 to the power of 9 plus 7 so one thing to observe is that even though there are 2 types of blocks which does increase the complexity of the problem that the board itself is quite thin in turn this actually greatly simplifies the problem we're trying to tackle because it restricts the number of block configurations we need to take into account let's look at a few examples of some tilings from the drawings below you can see that when the board is one unit wide there is exactly one solution and when N equals 2 there are exactly two solutions when we start getting to a board with the length of three things start getting slightly more interesting because now we're not only able to place dominoes but also Trauma knows in this situation we're able to tile the board in exactly five ways and when N equals four you can see that there are exactly eleven solutions you can find this problem on leet code with the ID domino and trauma note tiling I recommend you pause this video and attempt the problem before I reveal the solution remember that prac this is the best way for you to get better if you do get stuck I have two hints that might help unblock you my first hint is that the column index is likely one of the dimensions you might want to keep track of in your DP State my second hint is to observe a column slice of the board and identify how many possible states can arise from that one possible slice and try and see how that can fit into the problems solution in my last video we looked at an iterative solution to tiling Domino's on a grid in this video I want to switch things up a little bit and look at how to approach tiling problems recursively knowing how to solve a problem in more than one way opens up your options when it comes time to tackle new problems you have not seen before alright let's dive into the solution the first observation to make about this tiling problem is that you fully tile the board we must make sure that there are no gaps anywhere on the board as we tile the grid from left to right the first and the last boards on this slide are fully tiled but we missed a spot in the middle grid which we never want to do in many ways the necessity to have a fully tiled grid is an indication that our DP state should in some way capture a board partially filled up to some position without any gaps the two boards with the green arrows show boards which are completely filled with tiles from left to right up to a certain position this is what we want to track notice that the last board on the right is tiled out of order we don't want to do that tiling from left to right is generally the way to go apart from observing that our grids should be tiled without gaps and tiles from left to right you should also see for every column slice there can be at most four possible configurations either we're gonna have what I call state zero where neither row is tiled state one where the top row is tiled state 2 where the bottom row is tiled or state 3 where both rows are tiled with that we have enough information to track all partially filled States up to a certain index we can conclude that we only need two pieces of information first is index I the position up to which the board is fully tiled without gaps and second which of the four column States below is present at the rightmost extremity of the current state I want to note that a pairing of index I and the column state is meant to represent the number of ways to tile the board up to that state it doesn't represent the tiling of a particular arrangement of dominoes and trama nose in any way this is contradictory to what you might think that the drawings below are trying to imply remember that the goal is to count the total number of ways to tile the grid let's have a look at some examples of partial States on the left is the partial state at I equals 1 with column state 0 meaning no tiles are filled in the current column beside this is the partial state with I equals 3 and the column State 1 since only the top row is filled followed by the partial state at I equals 2 with only the bottom row filled and lastly is a partial state with I equals 3 and a full column state you might have noticed by now that state one and state two are symmetric and that state 0 at position I plus 1 is equal to state 3 at column position I so there's definitely some opportunity to save space and perform some kind of optimization that's not going to matter for this problem because the constraints are so small now that we understand how we are representing our partial states how do we transition from one partial state to another partial state unsurprisingly it's by placing dominoes and trauma knows however as we do so we need to make sure that we don't leave any gaps as we place blocks in the example on this slide the top and the bottom transitions are good but the middle transition leaves a gap in the grid which we do not want when placing the next block because of the shape of our dominoes and Trauma knows there are only four tiles on the extremity of the state that we ever end up filling I'm going to refer to these tiles as T 1 T 2 T 3 and T 4 as the frontier the frontier simply consists of the tiles that may possibly be tiled when we place the next block sometimes some of the tiles on the frontier are unavailable or blocked this can be the result of having previously placed a block or simply because part of the frontier reaches outside the bounds of the grid before we place a domino or trauma no we need to check if the tiles we want to use on the frontier are available below since T 1 and T 3 are available in the leftmost board we are able to place a horizontal Domino to generate the middle board similarly we can build off the last partial state by adding 8 Romano since T 2 T 3 and T 4 are all three one thing to notice here is that as we place blocks and fill the board that the frontier moves as blocks are placed alright now that we understand the main idea behind tiling the board let's have a look at some pseudocode don't be intimidated by the looks of the code it's actually quite simple I'll walk you through it first I define a few variables in the outer scope the first is the mod value which is 1 billion and 7 after the mod there is n the length of the board to tile this is given as input and after that there's the DP table which has n plus 1 rows and 4 columns for each of our column States assume that the table is initially filled with null values next up is the solve function which is basically a wrapper function for calling F the recursive function that does all the work F itself takes three pieces of information first I the index responsible for tracking how far along we've tiled the board the goal is to find the number of complete tilings for a board of science n additionally f also takes t1 and t2 as arguments which are boolean values which represent if tiles t1 and t2 are free on the horizon in the beginning t1 and t2 are free to be tiled which is why I pass in true and true when calling F now stepping inside F our base case is when we finish tiling the board which we have done once I equals n which means we have reached the end of the board the next thing I do is encode the column slice into a state number based on which tiles are blocked the make state function is actually very simple it returns the number associated with which column state is currently tiled if t1 is tiled we set the first bit to 1 and if t2 is tiled we set the second bit to 1 the result is that we have a number between 0 and 3 inclusive which represents the unique column state represented by t1 and t2 if you are unfamiliar with bit manipulations second make state function is another equivalent implementation which will encode a column state represented by t1 and t2 into a number with the column state and the current index we can check if we already know the number of ways to tile the current state and if we do then return that answer this is the part that makes the recursive implementation a dynamic programming solution rather than a brute-force because we are able to look up if we've already solved this particular subproblem and returned the answer immediately at this point we're going to try and tile the board based on the current state but first we need to know what the rest of the frontier looks like since the frontier always moves when we place a new block t3 and t4 are always available this is except for when they are outside the grid you may notice that the condition for t3 and t4 is the same so we could in theory combine t3 and t4 together into one variable representing the zone for t3 and t4 but I'm leaving them separate to avoid that confusion the variable count tracks the number of ways to tile the current state the various if conditions below simply place different tiles on the board depending on what the frontier looks like as those functions return we sum together the different ways to tie the board in the count variable in this first line we are trying to place a trauma no over the tiles t1 t2 and t3 if those three tiles are free we are able to place a trauma now and solve for a smaller subproblem once the trauma know has been placed we need to call F again to finish tiling the board when we call F we need to specify what the next column state looks like so we can move the frontier since our trauma no blocks the top tile we mark that t1 is unavailable however the next t2 tile is still free because nothing blocks it in the next line we place asymmetric trauma no so the only thing that changes is that we need to check if t4 is available and make sure that we block t2 in the next recursive call next we check if we can place a rotated trauma no when t2 is blocked before we place this rotated trauma no it is essential that we check that t2 is allready child since placing the trauma now without t2 being tiled would introduce a gap on the board then we have the same symmetric case only flipped on this next line we check if t1 and t2 are free and if so then we can place a vertical Domino in this situation t1 and t2 in the next column will both always be free so we can call F with true and true in this next line we check if all the tiles are free and attempt to place two horizontal tiles if we end up placing two horizontal tiles t1 and t2 in the next column will be fully blocked note that we don't need to check for the case where we want a place to vertical Domino's because that was accounted for in the previous if statement when we placed a single vertical Domino after that try and place a single horizontal Domino when t2 is blocked and do the same for the symmetric case again we need to explicitly check that t1 is blocked in order to avoid leaving a gap as we move over one column next we need to check the case where neither t1 nor t2 are free this case could happen for example when we place say two horizontal Domino's the very last thing we need to do is cash the solution and apply the mod and return the solution alright and that's all for tiling Domino's and trauma knows if you watched the previous video on tiling Domino's iteratively let me know if you prefer the iterative tiling approach or the recursive approach anyways thanks for watching please like this video if you learned something and subscribe for more mechanics engineer science videos I'll catch you