本文最后更新于：2022年11月20日 下午
题目描述
思路及实现
找规律
这种题吧，实际上就是画图找规律，跟求斐波那契数列没什么区别，把规律找出来想递归就递归想迭代就迭代。
那么重点就在于找规律了。从n=1开始，一直到n=5就差不多了，然后就会发现下面的式子：
dp[1]=1dp[2]=2dp[3]=dp[2]+dp[1]+2dp[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]⋅⋅⋅dp[n]=2∗dp[n−1]+dp[n−3],n≥4
规律找到了直接编程即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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装饰器，一是大量节省时间，二是防止超时（因为不加真的超了）。
下面是迭代法
1
2
3
4
5
6
7
8
9
10
11
| 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]
|
动态规划
正经dp不会，看官解。(逃
希望本文章能够帮到您~