力扣-790. 多米诺和托米诺平铺

本文最后更新于：2022年11月20日下午

题目描述

790

思路及实现

找规律

这种题吧，实际上就是画图找规律，跟求斐波那契数列没什么区别，把规律找出来想递归就递归想迭代就迭代。
那么重点就在于找规律了。从n=1开始，一直到n=5就差不多了，然后就会发现下面的式子：
$$
dp[1] = 1 \
dp[2] = 2 \
dp[3] = dp[2] + dp[1] + 2 \
dp[4] = dp[3] + dp[2] + 2 * dp[1] + 2 = 2 * dp[3] + dp[1] \
dp[5] = dp[4] + dp[3] + 2 * dp[2] + 2 * dp[1] + 2 = 2 * dp[4] + dp[2] \
\cdot\cdot\cdot \
dp[n] = 2 * dp[n - 1] + dp[n - 3],n \geq 4
$$
规律找到了直接编程即可。

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

        @lru_cache()
        def recursion(n: int) -> int:
            if n == 3:
                return 5
            elif n == 2:
                return 2
            elif n == 1:
                return 1
            else:
                return (2 * recursion(n - 1) + recursion(n - 3)) % mod

        return recursion(n)

不要忘记这种递归加上@lru_cache装饰器，一是大量节省时间，二是防止超时（因为不加真的超了）。
下面是迭代法

class Solution:
    def numTilings(self, n: int) -> int:
        mod = 10 ** 9 + 7
        i = 4
        dp = list([1, 2, 5])
        if n <= 3:
            return dp[n - 1]
        while i <= n:
            dp.append((2 * dp[i - 1 - 1] + dp[i - 3 - 1]) % mod)
            i += 1
        return dp[n - 1]