目錄鏈接：

力扣編程題-解法匯總_分享+記錄-CSDN博客

GitHub同步刷題項目：

https://github.com/September26/java-algorithms

原題鏈接：力扣

描述：

有兩種形狀的瓷磚：一種是?2 x 1?的多米諾形，另一種是形如?"L" 的托米諾形。兩種形狀都可以旋轉(zhuǎn)。

給定整數(shù) n ，返回可以平鋪?2 x n?的面板的方法的數(shù)量。返回對?109?+ 7?取模?的值。

平鋪指的是每個正方形都必須有瓷磚覆蓋。兩個平鋪不同，當(dāng)且僅當(dāng)面板上有四個方向上的相鄰單元中的兩個，使得恰好有一個平鋪有一個瓷磚占據(jù)兩個正方形。

示例 1:

輸入: n = 3 輸出: 5 解釋: 五種不同的方法如上所示。

示例 2:

輸入: n = 1 輸出: 1

提示：

• 1 <= n <= 1000

解題思路：

* 解題思路： * 這一定是一道動態(tài)規(guī)劃的題，如果我們?nèi)サ鬖型，那么就是一個斐波那契額數(shù)列，F(n)=F(n-1)+F(n-2) * 加上L形狀，我們?nèi)匀豢梢园凑者@個思路來。 * 開頭只有四種可能，-，=，L,「。 * -和=開頭的，我們可以歸結(jié)為斐波那契額數(shù)列，f(n)=f(n-1)+f(n-2) * L和「開頭的，我們可以歸結(jié)為一類問題，使用F(n)來表示，所以可以轉(zhuǎn)換為f(n)=f(n-1)+f(n-2)+F(n) * 我們再來看下F(n)怎解決？ * L開頭的話，只有兩種可能： * L開頭，以┐結(jié)尾，中間包含若干-形，其數(shù)量為f(n-3)+f(n-5)+f(n-7)... * L開頭，以」結(jié)尾，中間包含若干-形狀，其數(shù)量為f(n-4)+f(n-6)+f(n-8)... * 兩種類型累加，就是F(n)的數(shù)量。 * 最后，每次計算對值求模，得到我們想要的結(jié)果

代碼：

public class Solution790 {Map<Integer, Integer> fMap = new HashMap<>();int flag = 10_0000_0000 + 7;public int numTilings(int n) {fMap.put(0, 1);fMap.put(1, 1);fMap.put(2, 2);int index = 3;while (index <= n) {int indexValue = fMap.get(index - 1) % flag + fMap.get(index - 2) % flag;indexValue = indexValue % flag;indexValue += (2 * F(index)) % flag;indexValue = indexValue % flag;fMap.put(index, indexValue);index++;}return fMap.get(n);}private int F(int index) {//L開頭，」結(jié)尾int sum = 0;for (int i = 0; i <= index - 3; i += 2) {sum += fMap.get(index - 3 - i) % flag;sum = sum % flag;}if (index <= 3) {return sum;}for (int i = 0; i <= index - 4; i += 2) {sum += (fMap.get(index - 4 - i) % flag);sum = sum % flag;}//L開頭，┐結(jié)尾return sum;} }

總結(jié)

以上是生活随笔為你收集整理的​力扣解法汇总790. 多米诺和托米诺平铺的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。