Way to solve Tiling Problems

1. 10359 - Tiling



Given a board of size 2×n 
                                                              

Available tiles 2×1 and 2×2
Question: FInd the number of ways to completely fill the board.

E.g when n = 3 , 5ways

consider board of width n:

How can we fill the rightmost column :

1. By one 2×1 vertically.
2. By two 2×1 horizontally.
3. By one 2×2 either horizontally or vertically( since both are same).

Let f(n) be the number of ways of filling a board of size 2×n.

So f(n) = f(n-1) + f(n-2) + f(n-2)

Now, let's determine the base cases.
1. f(0) = 1, because if we have to find f(1) then , f(1) = f(0) + f(-1) + f(-1) , since f(-1) not exist, so  f(-1) = 0 then f(1) = f(0) + 0 + 0 => f(1) = f(0) 
since there is one way to fill the board of size 2×1 by using one 2×1 tile. It means that f(0) must 
be equal to 1.

2. f(1) = 1

Code: 
Complexity: O(n)

2. GNY07H - Tiling a Grid With Dominoes


Given a board of size 4×n.
Available tile 2×1
Question: FInd the number of ways to completely fill the board. 

E.g when n = 2 , 5ways

consider board of width n:

How can we fill the rightmost column:

1. By two 2×1 vertically.
2. By four 2×1 horizontally.
3. By two 2×1 horizontally in the bottom and one, 2×1 vertically in the top. 
4. By one 2×1 vertically in the bottom and two, 2×1 horizontally in the top. 
Note: Both 3 and 4 are the same, the only difference is that, the positions but the number of ways of 3 = number of ways of 4.
5. By one 2×1 horizontally in the top, one 2×1 vertically in the middle and one 2×1 in the bottom.

Let f(n) be the number of ways of filling a board of size 4×n.
Let g(n) be the number of ways of filling a board of size 4×n of this type.

Let h(n) be the number of ways of filling a board of size 4×n of this type.

So f(n) = f(n-1) + f(n-2) + g(n-2) + g(n-2) + h(n-2)


🤓Now let's find g(n).

How can we fill the vacant 2×1 space in g(n):


1. By one 2×1 vertically, then the shape after doing this will be like f(n)
2. By adding two 2×1 horizontally, then the shape after doing this will like g(n-1)


So, g(n) = f(n) + g(n-1)


🤓Now let's find h(n).

How can we fill the vacant 2×1 space in h(n):


1. By one 2×1 vertically, then the shape after doing this will be like f(n)

2. By adding two 2×1 horizontally.
But this shape doesn't like any of  f, g or h. So we have to do something so that its shape will belong to any of f, g or h type.

If one 2×1 horizontally on top and one 2×1 horizontally in the bottom will add, then its shape will similar to h.


So, h(n) = f(n) + h(n-2)

Now, let's determine the base cases.
1. f(0) = 1
2. f(1) = 1
3. g(0) = f(0) + g(-1) = 1 + 0 = 1
4. g(1) = f(1) + g(0) = 1 + 1 = 2
5. h(0) = f(0) + h(-2) = 1 + 0 = 1
6. h(1) = f(1) + h(-1) = 1 + 0 = 1

Code:


Complexity: O(n)


Happy coding!👨‍💻

2 comments:

Powered by Blogger.