> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/tiling-with-dominoes.md).

# Tiling with Dominoes

Given a *3 x n* board, find the number of ways to fill it with *2 x 1* dominoes.

***Example 1***\
Following are all the **3** possible ways to fill up a **3 x 2** board.<br>

![](https://media.geeksforgeeks.org/wp-content/uploads/example1-3-300x113.png)

***Example 2***\
Here is one possible way of filling a 3 x 8 board. You have to find all the possible ways to do so.\
\
**Examples :**

![](https://media.geeksforgeeks.org/wp-content/uploads/example_3x8-300x113.jpg)

```
Input : 2
Output : 3

Input : 8
Output : 153

Input : 12
Output : 2131
```

**Approach:**

**Defining Subproblems:**\
At any point while filling the board, there are three possible states that the last column can be in:<br>

![](https://media.geeksforgeeks.org/wp-content/uploads/possibleStates-1-1024x327.jpg)

```
An =  No. of ways to completely fill a 3 x n board. (We need to find this)
Bn =  No. of ways to fill a 3 x n board with top corner in last column not filled.
Cn =  No. of ways to fill a 3 x n board with bottom corner in last column not filled.
```

**Note:** The following states are impossible to reach:

![](https://media.geeksforgeeks.org/wp-content/uploads/impossibleStates-300x127.jpg)

**Finding Reccurences**\
**Note:** Even though **Bn** and **Cn** are different states, they will be equal for same **‘n’**. *i.e* **Bn = Cn**\
Hence, we only need to calculate one of them.

**Calculating An:**

![](https://media.geeksforgeeks.org/wp-content/uploads/An-1024x186.jpg)

![ A\_{n} = A\_{n-2} + B\_{n-1} + C\_{n-1}  ](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-bcaa6e659b56fd9c96b21cc8d5792e94_l3.svg)

![ A\_{n} = A\_{n-2} + 2\*(B\_{n-1}) ](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-86dbf9effaffd53dfed218683dd62e42_l3.svg)

**Calculating Bn:**

![ B\_{n} = A\_{n-1} + B\_{n-2} ](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-0ff897fdb1fa7d38a5c18e70fbec6bed_l3.svg)

![](https://media.geeksforgeeks.org/wp-content/uploads/Bn-1024x186.jpg)

```java
class Solution {
    // For explaination look at GFG article
    public static int triTiling(int n) {
        int[] A = new int[n + 1];
        int[] B = new int[n + 1];
        A[0] = 1;
        A[1] = 0;
        B[0] = 0;
        B[1] = 1;
        for (int i = 2; i <= n; i++) {
            A[i] = A[i - 2] + 2 * B[i - 1];
            B[i] = A[i - 1] + B[i - 2];
        }
        return A[n];
    }
}
```