# LeetCode 790: Domino and Tromino Tiling

## Problem Restatement

We are given an integer `n`.

We need to count how many ways there are to tile a `2 x n` board using two tile types:

| Tile | Shape |
|---|---|
| Domino | Covers 2 squares in a straight line |
| Tromino | Covers 3 squares in an L shape |

Both tile types may be rotated.

Return the number of tilings modulo:

```python
10**9 + 7
```

Every square must be covered exactly once. Two tilings are different if their tile placements differ.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Number of ways to tile a `2 x n` board |
| Tiles | `2 x 1` dominoes and L-shaped trominoes |
| Rotation | Allowed |
| Modulo | `10^9 + 7` |

Function shape:

```python
class Solution:
    def numTilings(self, n: int) -> int:
        ...
```

## Examples

Example 1:

```python
n = 3
```

There are `5` ways to tile a `2 x 3` board.

So the answer is:

```python
5
```

Example 2:

```python
n = 1
```

Only one vertical domino can cover a `2 x 1` board.

So the answer is:

```python
1
```

## First Thought: Build Boards Recursively

A direct idea is to place a tile in the leftmost uncovered cell and recursively fill the rest.

This works for small `n`, but it creates many repeated subproblems.

For example, many different early placements can leave the same remaining board shape. We should store the number of ways for each board width and state.

## Key Insight

When tiling from left to right, the board can be in two important states.

| State | Meaning |
|---|---|
| `full[i]` | Number of ways to fully tile a `2 x i` board |
| `partial[i]` | Number of ways to tile a `2 x i` board with one missing corner cell |

The missing corner may be the top or bottom cell. These two cases are symmetric, so one variable is enough.

Now derive the transitions.

To fully tile width `i`:

1. Add one vertical domino to a full `2 x (i - 1)` board.
2. Add two horizontal dominoes to a full `2 x (i - 2)` board.
3. Add one tromino to one of two partial states of width `i - 1`.

So:

```python
full[i] = full[i - 1] + full[i - 2] + 2 * partial[i - 1]
```

To create a partial state of width `i`:

1. Extend a full `2 x (i - 2)` board with one tromino.
2. Extend a partial `2 x (i - 1)` board with one horizontal domino.

So:

```python
partial[i] = full[i - 2] + partial[i - 1]
```

## Algorithm

Use dynamic programming.

Base cases:

```python
full[0] = 1
full[1] = 1
partial[0] = 0
partial[1] = 0
```

Then for `i` from `2` to `n`:

```python
full[i] = full[i - 1] + full[i - 2] + 2 * partial[i - 1]
partial[i] = partial[i - 1] + full[i - 2]
```

Return:

```python
full[n]
```

## Correctness

We prove that `full[i]` stores the number of ways to fully tile a `2 x i` board, and `partial[i]` stores the number of ways to tile a `2 x i` board with exactly one missing corner cell.

The base cases are correct. An empty board has one complete tiling, so `full[0] = 1`. A `2 x 1` board has exactly one complete tiling, using one vertical domino, so `full[1] = 1`. A partial board of width `0` or `1` cannot be formed in the needed way, so the partial values start at `0`.

For `full[i]`, consider the right end of a complete tiling. If the last column is covered by a vertical domino, the remaining board is a full `2 x (i - 1)` board. If the last two columns are covered by two horizontal dominoes, the remaining board is a full `2 x (i - 2)` board. Otherwise, the final completion must use a tromino to fill a previous partial state. There are two symmetric partial states, top-missing and bottom-missing, so this contributes `2 * partial[i - 1]`.

For `partial[i]`, the missing corner can be formed either from a full `2 x (i - 2)` board by placing one tromino, or from a smaller partial state by extending it with one horizontal domino. These two cases are disjoint and cover all ways to create such a partial boundary.

Thus the transitions count every valid tiling exactly once. Therefore, `full[n]` is the number of complete tilings of the `2 x n` board.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We compute each width once |
| Space | `O(n)` | Arrays store DP values for all widths |

The space can be reduced to `O(1)` because each step uses only the previous two full values and the previous partial value.

## Implementation

```python
class Solution:
    def numTilings(self, n: int) -> int:
        mod = 10**9 + 7

        if n == 1:
            return 1

        full = [0] * (n + 1)
        partial = [0] * (n + 1)

        full[0] = 1
        full[1] = 1

        for i in range(2, n + 1):
            full[i] = (
                full[i - 1]
                + full[i - 2]
                + 2 * partial[i - 1]
            ) % mod

            partial[i] = (
                partial[i - 1]
                + full[i - 2]
            ) % mod

        return full[n]
```

## Code Explanation

We use the required modulo:

```python
mod = 10**9 + 7
```

The complete tiling array is:

```python
full = [0] * (n + 1)
```

The partial tiling array is:

```python
partial = [0] * (n + 1)
```

The base cases are:

```python
full[0] = 1
full[1] = 1
```

Then we compute every board width from left to right:

```python
for i in range(2, n + 1):
```

The complete state transition is:

```python
full[i] = (
    full[i - 1]
    + full[i - 2]
    + 2 * partial[i - 1]
) % mod
```

The partial state transition is:

```python
partial[i] = (
    partial[i - 1]
    + full[i - 2]
) % mod
```

Finally, the answer is the number of complete tilings:

```python
return full[n]
```

## Space-Optimized Version

There is also a one-state recurrence:

```python
dp[i] = 2 * dp[i - 1] + dp[i - 3]
```

with:

```python
dp[1] = 1
dp[2] = 2
dp[3] = 5
```

Implementation:

```python
class Solution:
    def numTilings(self, n: int) -> int:
        mod = 10**9 + 7

        if n <= 2:
            return n

        a = 1
        b = 2
        c = 5

        if n == 3:
            return c

        for _ in range(4, n + 1):
            a, b, c = b, c, (2 * c + a) % mod

        return c
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numTilings(1) == 1
    assert s.numTilings(2) == 2
    assert s.numTilings(3) == 5
    assert s.numTilings(4) == 11
    assert s.numTilings(5) == 24

    print("all tests passed")

run_tests()
```

Test coverage:

| Test | Why |
|---|---|
| `n = 1` | Smallest board |
| `n = 2` | Only domino-based tilings |
| `n = 3` | First case where trominoes matter |
| `n = 4` | Checks recurrence after base cases |
| `n = 5` | Checks continued DP growth |