多米诺和托米诺平铺
问题描述：
有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 “L” 的托米诺形。两种形状都可以旋转。
给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:
输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1
输出: 1
问题求解：
class Solution {
int mod=(int)1e9+7,matrix[][]={{0,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,1}};
public int numTilings(int n) {
long ans[][]=new long[n][4];
ans[0]=new long[]{1,0,0,1};
for(int i=1;i<n;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){ans[i][j]+=ans[i-1][k]*matrix[k][j];}
ans[i][j]%=mod;
}
}
return (int)ans[n-1][3];
}
}
问题总结：
老规矩我们先看一下官方求解。
方法一：动态规划
考虑这么一种平铺的方式：在第 ii 列前面的正方形都被瓷砖覆盖，在第 ii 列后面的正方形都没有被瓷砖覆盖（ii 从 11 开始计数）。那么第 ii 列的正方形有四种被覆盖的情况：
一个正方形都没有被覆盖，记为状态 00；
只有上方的正方形被覆盖，记为状态 11；
只有下方的正方形被覆盖，记为状态 22；
上下两个正方形都被覆盖，记为状态 33。
使用 \textit{dp}[i][s]dp[i][s] 表示平铺到第 ii 列时，各个状态 ss 对应的平铺方法数量。考虑第 i-1i−1 列和第 ii 列正方形，它们之间的状态转移如下图（红色条表示新铺的瓷砖）：
初始时 \textit{dp}[0][0] = 0, \textit{dp}[0][1] = 0, \textit{dp}[0][2] = 0, \textit{dp}[0][3] = 1dp[0][0]=0,dp[0][1]=0,dp[0][2]=0,dp[0][3]=1，对应的状态转移方程（i \gt 0i>0）为：
\begin{aligned} \textit{dp}[i][0] &= \textit{dp}[i-1][3] \ \textit{dp}[i][1] &= \textit{dp}[i-1][0] + \textit{dp}[i-1][2] \ \textit{dp}[i][2] &= \textit{dp}[i-1][0] + \textit{dp}[i-1][1] \ \textit{dp}[i][3] &= \textit{dp}[i-1][0] + \textit{dp}[i-1][1] + \textit{dp}[i-1][2] + \textit{dp}[i-1][3] \ \end{aligned}
dp[i][0]
dp[i][1]
dp[i][2]
dp[i][3]
=dp[i−1][3]
=dp[i−1][0]+dp[i−1][2]
=dp[i−1][0]+dp[i−1][1]
=dp[i−1][0]+dp[i−1][1]+dp[i−1][2]+dp[i−1][3]
最后平铺到第 nn 列时，上下两个正方形都被覆盖的状态 \textit{dp}[n][3]dp[n][3] 对应的平铺方法数量就是总平铺方法数量。
Original: https://blog.csdn.net/weixin_43401773/article/details/127818735
Author: Chen三变
Title: 第二十一天多米诺和托米诺平铺
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/654830/
转载文章受原作者版权保护。转载请注明原作者出处！