#### 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!👨‍💻

1. 1. 