Tiling problems [2/2] | Dynamic Programming

Key Takeaways

[Music] hello everyone and welcome back this is william and today we're going to continue to explore a generalization of the block tiling problem we saw in the last video previously we looked at how to tile a 1 by n board with tiles of lengths one and two we observed that the recurrence f of n equals f of n minus one plus f of n minus two gave the number of tilings for a board of length n today we're going to ask the generalization of the problem which is how do we count the number of tilings when we have blocks of different lengths and blocks of the same length but different colors again you can assume that there is an infinite amount of each block size and color for instance as you can imagine there are numerous ways to tile a board of length seven with the four different block sizes displayed above you can have a purple block a red block a purple block followed by a green block or maybe two red blocks two purple blocks a blue block followed by a red block and so on let's define the function f of n to be the number of tilings for a board of length n my question for you is what is the value of f of 25 that is how many ways are there to tile a board of length 25 with the tiles displayed on this screen i'll give you a moment to think about it but here are a few hints to get you started f of one equals two f of two equals five and f of 7 equals 452 i encourage you to pause the video here and give the problem a try i'm going to reveal the solution in the following slide so according to my calculations f of 25 is a pretty large number five billion three hundred thirty one million one hundred thirty three thousand six hundred twenty six it's actually not uncommon for these combinatorial dynamic programming problems to yield such large results because the answers tend to grow very quickly the approach we're going to use to calculate f n is to construct all the ways to tile boards of length 1 then construct all the ways to make boards of length 2 then all boards of length 3 and so on as we do this you'll notice that we will be able to reuse smaller known board tiling solutions to construct larger boards we're going to look at how to solve the problem using the bottom-up approach we looked at in the last video first we need to consider all the ways there are to tile a board of length zero that may sound trivial but it's the base case or the foundation by which our dynamic programming solution is based off of so there's exactly one way to make a board of length zero and that's to have the empty board state from the empty state there are exactly two ways to make a board of length one we can either tile the board of length one using a red block or tile a board of length one using a purple block there are no other ways to make a board of length one because our other tiles the blue and green tiles are too large to even fit on the board at the moment next we're going to construct all the boards of length 2. to do this we are going to reuse all the solutions from boards of length 1 to construct boards of length 2 by appending a red block to all the solutions as well as a purple block you will notice that we are able to create a board with a blue tile for the first time one way to think about this is that we are adding a blue tile to the empty state to create a board of length two now you can see that there are exactly five ways to create a board of length two next we are going to construct all boards of length three similar to before we are going to use all the board tilings of length two to create boards of length three by adding a red and purple tile we are also going to reuse all boards of length 1 plus a blue tile to create a board of length 3. you may already be seeing pattern here but essentially for every block of length k that fits on the board we are going to add on all the solutions from k columns ago and add them to the current tiling count so in this situation there is 5 plus 5 plus 2 for a total of 12 tilings of length 3. based on the previous example try and determine how many ways there are to tile a board of length 4. pause the video if you need more time in order to find all the tilings for a board of length four a pen blocks to the existing solutions from previous board sizes which result in a board of length four so in total there are 30 ways to tile a board of length 4. let's take a look at how we might discover the recurrence relation to count the number of board tilings the realization from the previous example is that we can reuse already known solutions from smaller board sizes to compute f n for instance suppose we have a tile of length k that we can use to fill boards if we get all the tilings of length and the minus k and append a block of length k then we have just generated a new unique set of tilings of length n using the block of size k if you assume that we only had a single block of length k to tile boards with then the recurrence would be pretty simple it would be f of n equals f of n minus k however if we added another block of length h to our set of available blocks then the recurrence would become f of n equals f of n minus k plus f of n minus h because blocks of length h are a different color they generate their own unique set of tilings that need to be accounted for in their recurrence coming back to our original question what is the recurrence when we have two blocks of length one one block of length two and one block of length four well in this case the recurrence is f of n equals f of n minus one for the red block plus f of n minus one for the purple block plus f of n minus two for the blue block plus f of n minus four for the green block since f of n minus one is repeated we can further simplify the recurrence by combining the f of n minus 1 terms this brings us to the generalization of the problem and as we attempt to derive a general solution we quickly discover that the recurrence relation is due to two important factors first the length of the tiles at our disposal and secondly the frequency of the tile lengths using that information we are able to conjure up a linear recurrence which incorporates the lengths of the tiles and the frequency of the tile lengths the length of the tiles is used to determine the offset in the function to get the board length and the frequency of the tile lengths is used to determine the coefficients in front of the terms in the linear recurrence all right let's take a look at some pseudo code on how to implement the generalized tiling recurrence let's begin with the iterative solution this is the code for the iterative solution the approach here is to use the bottom-up solution presented earlier let's walk through it as input we provide n the board length we want to solve for as well as the list containing the tile lengths of all the tiles we have at our disposal in the example at the beginning of the video we would have specified n equals 25 and the tiles list equal to the numbers 1 1 2 and 4. to start with i declare an array called dp of length n plus 1 to store all the solutions for the values of f of n since we know the value for f of 0 we immediately set the value of f of 0 to equal 1 as the base case the next thing i do is declare a map data structure called tile frequency which counts the frequency of each tile at length then i iterate over all the tiles and count the frequency of each tile length in this loop the variable i represents the board length so we iterate from i equals one meaning a board of size 1 up to a board of size n then inside the loop we loop through all the unique tile lengths then we skip the tiles which are larger than the current board size since they can't fit on the board and sum up the number of ways to tile the board by adding up all the values in the linear recurrence to do this we need to add up the number of ways to tile the board at the current length minus the tile size and multiplied by the frequency of the tile length after the loops have completed the dp array should be populated and we can return the value of f of n let's also have a look at the recursive implementation i think it's important to understand how to implement a problem in more than one way to expand how you approach certain problems sometimes a problem will be easier for you if you think about it iteratively sometimes it'll be easier for you if you think about it recursively the idea behind the recursive implementation is largely the same concept except that instead of solving the problem bottom up we're going to be solving it top down to do that we are going to break the board down into smaller boards instead of building larger boards from smaller boards on the first line i declare a map called dp which maps the board length to the tile count this is where we will be storing our solutions i decided to use a map instead of an array because it's possible that the number of sub-problems is very small this can happen when the tile size is quite large and by using a map we can save some memory when the value of n is very big the recursive implementation takes the same inputs as the iterative approach and the board size and the tiles array inside the solve function all i do is stage a call to the recursive function f in addition to the board length i also provide the tile frequency map as another argument to the function which gets calculated below in the compute tile frequency method first we declare a map called tf short for tile frequency which maps the tile length to the number of tiles of that length then we do a simple loop through the tiles and compute the frequency for each tile length now let's take a look at the recursive function itself which is what actually computes the different board tiling configurations as input to the function we provide n the current board length and tf the tile frequency of each tile length the time frequency map is actually constant you could pull it out to simplify this function if you wanted to the first thing i do is check if the board length is negative if so return 0 to indicate that we were able to produce 0 board tilings it is possible to get a negative board length when we subtract the tile length from the board size and the recursive call below next we check if we have successfully completed tiling a board if so we can return that there is exactly one way to tie the board using the tiles that were placed the next thing we do is check the cache to see if we have already computed the solution for f of n and return a result if we have this is the optimization that really speeds up the recursive implementation since we're avoiding recomputing already known solutions to subproblems afterwards we actually compute the number of different ways to tie the board to do this we compute the solution for f of n using the linear recurrence relation described previously this involves looping through the tiles of different lengths and summing up the solutions for all the smaller board sizes we were able to create taking into account the frequency of each tile length after all the recursive calls have finished we can cache the solution for f n and return the tile count all right and that's all for board tilings thank you for watching uh i hope you learned something and catch you next time please remember to like this video and subscribe for more mathematics and computer science content thank you