Сложность: medium
У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры.
Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
При укладке каждая клетка должна быть покрыта плиткой. Две укладки считаются разными, если и только если есть две 4-направленно смежные клетки на доске, такие, что в одной укладке обе клетки заняты плиткой, а в другой - нет.
Пример:
Input: n = 3
Output: 5
Explanation: The five different ways are show above.
👨💻 Алгоритм:
1⃣Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n).
2⃣Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор @cache автоматически поддерживает эти хэшмапы для нас.
3⃣Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся.
😎 Решение:
class Solution {
private $MOD = 1_000_000_007;
private $fCache = [];
private $pCache = [];
private function p($n) {
if (isset($this->pCache[$n])) {
return $this->pCache[$n];
}
if ($n == 2) {
return 1;
}
$result = ($this->p($n - 1) + $this->f($n - 2)) % $this->MOD;
$this->pCache[$n] = $result;
return $result;
}
private function f($n) {
if (isset($this->fCache[$n])) {
return $this->fCache[$n];
}
if ($n <= 2) {
return $n;
}
$result = ($this->f($n - 1) + $this->f($n - 2) + 2 * $this->p($n - 1)) % $this->MOD;
$this->fCache[$n] = $result;
return $result;
}
public function numTilings($n) {
return $this->f($n);
}
}Ставь 👍 и забирай 📚 Базу знаний