标签: 动态规划
难度: Medium
有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。
给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:
输入: n = 3 输出: 5 解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1 输出: 1
提示：
1 <= n <= 1000运行时间: 26 ms
内存: 16.0 MB
Mod = 10**9+7
class Solution:
def numTilings(self, n: int) -> int:
if n == 1:
return 1
f = [0]*(n+1)
f[0] = f[1] = 1
f[2] = 2
for i in range(3,n+1):
f[i] = (f[i-1]*2+f[i-3])%Mod
return f[-1]
这个题解使用动态规划的思路来解决多米诺和托米诺平铺问题。通过观察可以发现，对于第i列，其状态只与前三列(i-1, i-2, i-3)有关。因此，可以使用一个一维数组f来记录状态，其中f[i]表示平铺2 x i的面板的方法数量。初始条件为f[0]=f[1]=1，f[2]=2。对于i>2的情况，可以通过状态转移方程f[i] = (f[i-1]*2+f[i-3]) mod 10^9+7来计算f[i]的值，最终返回f[n]即可得到答案。
时间复杂度: O(n)
空间复杂度: O(n)
Mod = 10**9+7
class Solution:
def numTilings(self, n: int) -> int:
if n == 1:
return 1
f = [0]*(n+1) # 创建一个长度为n+1的数组f用于存储状态
f[0] = f[1] = 1 # 初始条件：平铺2x0和2x1的面板的方法数为1
f[2] = 2 # 初始条件：平铺2x2的面板的方法数为2
for i in range(3,n+1): # 从i=3开始遍历到n
f[i] = (f[i-1]*2+f[i-3])%Mod # 状态转移方程：f[i] = (f[i-1]*2+f[i-3]) mod 10^9+7
return f[-1] # 返回f[n]即为最终答案
状态转移方程`f[i] = f[i-1]*2 + f[i-3]`的逻辑是基于不同的平铺方式组合。考虑最后一列的可能形态：1. 一个竖直的多米诺瓷砖（占据最后一个单元格的两行），此时剩余部分是`f[i-1]`的情况，因为它不影响前面的平铺方式。但这样的瓷砖可以放在任意一个单元格中，所以存在2个这样的场景。2. 使用两个托米诺瓷砖（一个横放在底部，一个横放在顶部），这种情况会影响到前三列，因此这种情况下的可能性由`f[i-3]`表示。总结起来，`f[i]`的计算包括从i-1列转移而来的可能性（乘以2因为多米诺瓷砖有两种放置方式）和从i-3列转移而来的托米诺特殊排列。
在动态规划中，`f[0] = 1`通常用作一个数学上的便利，表示一个空的平铺方法。虽然实际上2x0的面板在物理世界中不存在，但在数学建模中，我们认为存在一种“不做任何事”的方法来平铺一个空面板，这有助于简化和初始化递推关系的边界条件。
是的，给出的动态规划解法考虑了所有可能的瓷砖组合，包括多米诺和托米诺的所有可能排列。通过构建状态转移方程，考虑了每一列可能以竖直多米诺瓷砖结束或者以两个水平托米诺瓷砖结束的情况，确保了包括所有有效的平铺方式。
平铺2x2面板有两种方法：1. 使用两个竖直的多米诺瓷砖，每个分别放在两列中。2. 使用两个横向的托米诺瓷砖，一个放在顶部两格，另一个放在底部两格。这两种不同的配置方式确保了使用这些瓷砖可以完全覆盖2x2的面板，因此`f[2] = 2`。