Сложность: 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 val MOD = 1_000_000_007
private val fCache = mutableMapOf<Int, Int>()
private val pCache = mutableMapOf<Int, Int>()
private fun p(n: Int): Int {
if (pCache.containsKey(n)) {
return pCache[n]!!
}
if (n == 2) {
return 1
}
val result = (p(n - 1) + f(n - 2)) % MOD
pCache[n] = result
return result
}
private fun f(n: Int): Int {
if (fCache.containsKey(n)) {
return fCache[n]!!
}
if (n <= 2) {
return n
}
val result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD
fCache[n] = result
return result
}
fun numTilings(n: Int): Int {
return f(n)
}
}Ставь 👍 и забирай 📚 Базу знаний