Замощение домино и тримино

Задача.

У вас есть два вида плиток:

домино — прямоугольник 2 × 1;

тримино — L-образная плитка, состоящая из трёх клеток.

Обе плитки можно свободно поворачивать.

По данному целому n определите, сколькими способами можно замостить доску 2×n этими плитками. Поскольку ответ может быть очень большим, выведите его по модулю 10^9 + 7.

Замощением считается такое покрытие, при котором каждая клетка доски закрыта плиткой. Два замощения считаются разными, если существует пара клеток, соприкасающихся сторонами, которые в одном замощении укрыты одной плиткой, а в другом — двумя разными.

Например, для n = 3 таких замощений 5, как показано на картинке

Ссылка на leetcode: https://leetcode.com/problems/domino-and-tromino-tiling

Решение.

Когда в условии есть фраза "number of ways (число способов)" это верный признак того, что это задача на динамическое программирование.
Эта задача не исключение.

Давайте сначала попробуем руками "пощупать" различные варианты для малых n.

n = 0 -> 0

n = 1 -> 1.

n = 2 -> 2

n = 3 -> 5

Определим состояния

dp[i] — количество способов полностью замостить доску размером 2×i. Полностью означает, что не останется ни одной пустой клетки.

Введём ещё одно, второе, состояние — p[i] — количество способов замостить доску размером 2×i не полностью. Не полностью означает, что заполнены все клетки, кроме одной — последней в верхнем правом углу.
Например,

Соотношения

Выведем формулы для вычисление dp[i] и p[i].

Получить замощение доски 2×i можно 4 способами из предыдущих:

из двух разных частичных состояния p[i-1] методом добавления тримино, которые повернуты по разному:

Добавлением вертикального домино к dp[i-1]:

И наконец, добавление 2 горизонтальным домино к dp[i-2]:

Т.е. dp[i] = dp[i - 1] + dp[i - 2] + 2 * p[i - 1].

Теперь формула для p[i].

Получить p[i] можно 2 способами:

1 - из полностью замощенной доски 2x(i-2) добавив тримино:

2 - Добавив горизонтальное домино к частично замощенной доске p[i-1]:

Т.е. p[i] = p[i - 1] + dp[i - 2].

Реализация

class Solution {
    public int numTilings(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        long dp[] = new long[n + 1];
        long p[] = new long[n + 1];

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        p[0] = 0;
        p[1] = 0;
        p[2] = 1;

        int modulo = 1000000007;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + 2 * p[i - 1]) % modulo;
            p[i] = (p[i - 1] + dp[i - 2]) % modulo;
        }
        return (int)dp[n];
    }
}

Time Complexity = O(N)
Space Complexity = O(N)