文章目錄

• 1 題目理解
• 2 動(dòng)態(tài)規(guī)劃
• • 2.1只有一種板
  • 2.2 有兩種板

1 題目理解

We have two types of tiles: a 2x1 domino shape, and an “L” tromino shape. These shapes may be rotated.

XX <- domino

XX <- “L” tromino
X
Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 7.

(In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.)

Example:
Input: 3
Output: 5
Explanation:
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
Note:

N will be in range [1, 1000].

輸入：正整數(shù)N
輸出：能夠組成2xN 的一個(gè)長(zhǎng)方形，有幾種方式。
規(guī)則：積木類型有兩種：一種是XX，domino板；一種是
XX
X
tromino板。返回的結(jié)果應(yīng)該是對(duì)$10^9+7$取余。
這個(gè)題目，從題目理解就很費(fèi)解。還是看了花花醬的解釋才明白怎么回事。一種積木是長(zhǎng)方形，一種積木是L行。每次是在前一個(gè)狀態(tài)上，追加這兩種板的其中一種或者兩種。最終拼成一個(gè)2xn的長(zhǎng)方形。

2 動(dòng)態(tài)規(guī)劃

2.1只有一種板

如果只有一種domino板，有多少種方式鋪滿一個(gè)2xn的長(zhǎng)方形呢？

畫(huà)圖之后發(fā)現(xiàn)dp[i] = dp[i-1]+dp[i-2]，是一個(gè)菲波那切數(shù)列。初始化：dp[0]=1,dp[1]=1。答案是：dp[n]。

2.2 有兩種板

如果有兩種版，domino板和tromino板。
在處理第i步的時(shí)候，對(duì)于前i-1形成的圖像可能分成三種情況。
一種情況是前i-1步以后，第i-1列，上下兩行都有板。

一種情況是前i-1步以后，第i-1列，上面一行有板。（看灰色部分）

一種情況是前i-1步以后，第i-1列，下面一行有板。（看灰色部分）

我們定義數(shù)組in[N+1][3] dp。dp[i][0]表示第i列，上下行都有板。dp[i][1]表示第i列，上面行有板。dp[i][2]表示第i列，下面行有板。

那么分析要到達(dá)dp[i][0]有哪些可能性，或者說(shuō)從哪些狀態(tài)能到達(dá)dp[i][0]。

如圖所示，第一個(gè)需要一塊domino板，第二個(gè)需要2塊domino板，第3個(gè)需要一塊tromino板，第4個(gè)需要一塊tromino板。

所以遞歸方程為：dp[i][0] = dp[i-1][0] + dp[i-2][0] + dp[i-1][1] + dp[i-1][2]

接著分析要到達(dá)dp[i][1]有哪些可能性，或者說(shuō)從哪些狀態(tài)能到達(dá)dp[i][1]。

遞歸方程：dp[i][1] = dp[i-2][0] + dp[i-1][2]

最后分析要到達(dá)dp[i][2]有哪些可能性，或者說(shuō)從哪些狀態(tài)能到達(dá)dp[i][2]。

遞歸方程：dp[i][2] = dp[i-2][0] + dp[i-1][1]

編碼解決

class Solution {public int numTilings(int N) {long[][] dp = new long[N+1][3];dp[0][0] = dp[1][0] = 1;int kMod = 1000000007;for(int i=2;i<=N;i++){dp[i][0] = (dp[i-1][0] + dp[i-2][0] + dp[i-1][1] + dp[i-1][2])%kMod;dp[i][1] = (dp[i-2][0] + dp[i-1][2])%kMod;dp[i][2] = (dp[i-2][0] + dp[i-1][1])%kMod;}return (int)dp[N][0];} }

時(shí)間復(fù)雜度O(n)

總結(jié)

以上是生活随笔為你收集整理的790. Domino and Tromino Tiling的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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