题目链接790. 多米诺和托米诺平铺 - 力扣LeetCode题目描述有两种形状的瓷砖一种是2 x 1的多米诺形另一种是形如 “L” 的托米诺形。两种形状都可以旋转。给定整数 n 返回可以平铺2 x n的面板的方法的数量。返回对109 7取模 的值。平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同当且仅当面板上有四个方向上的相邻单元中的两个使得恰好有一个平铺有一个瓷砖占据两个正方形。题目示例示例 1 :输入: n 3 输出: 5 解释: 五种不同的方法如上所示。示例 2 :输入: n 1 输出: 1解题思路问题理解给定一个2 x n的面板需要用两种类型的瓷砖2x1和L形完全覆盖。瓷砖可以旋转四种方向但必须完全覆盖面板且不重叠。需要计算所有可能的平铺方式数结果对10^9 7取模。动态规划思路定义f[i]为2 x i面板的平铺方式数。初始条件f[0] 1无实际意义辅助计算f[1] 1只能竖着放一块2x1瓷砖f[2] 2两块竖着或两块横着状态转移方程对于i 3f[i] 2 * f[i-1] f[i-3]。解释2 * f[i-1]在2 x (i-1)的基础上添加一块竖着的2x1瓷砖或两块横着的2x1瓷砖。f[i-3]在2 x (i-3)的基础上添加一个L形瓷砖的组合。模数处理由于结果可能非常大每次计算后对MOD 10^9 7取模防止整数溢出题解代码class Solution{private static final int MOD1_000_000_007;// 定义模数防止整数溢出 public int numTilings(int n){if(n1){return1;// 当n1时只有一种平铺方式}long[]fnew long[n 1];// 动态规划数组f[i]表示2xi面板的平铺方式数 f[0]f[1]1;// 初始化f[0]无实际意义f[1]1f[2]2;// 当n2时有两种平铺方式for(int i3;in;i){// 状态转移方程f[i]2*f[i-1] f[i-3]f[i](f[i -1]*2 f[i -3])% MOD;// 每次计算后取模}return(int)f[n];// 返回结果转换为int类型}}复杂度分析时间复杂度需要计算f[1]到f[n]共n次循环。每次循环的计算是O(1)操作乘法和加法。总时间复杂度为O(n)。空间复杂度使用了一个长度为n 1的数组f因此空间复杂度为O(n)。可以优化为O(1)因为只需要保存前三个状态f[i-1]、f[i-2]、f[i-3]。