domino-and-tromino-tiling

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You have two types of tiles: a <code>2 x 1</code> domino shape and a tromino shape. You may rotate these shapes.
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/15/lc-domino.jpg" style="width: 362px; height: 195px;" />
Given an integer n, return the number of ways to tile an <code>2 x n</code> board. Since the answer may be very large, return it modulo <code>109 + 7</code>.

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.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/15/lc-domino1.jpg" style="width: 500px; height: 226px;" />
<pre>
Input: n = 3
Output: 5
Explanation: The five different ways are show above.
</pre>

Example 2:

<pre>
Input: n = 1
Output: 1
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

numTilings

Domino and Tromino Tiling

Dynamic Programming

有两种形状的瓷砖：一种是&nbsp;<code>2 x 1</code> 的多米诺形，另一种是形如&nbsp;"L" 的托米诺形。两种形状都可以旋转。

<img src="https://assets.leetcode.com/uploads/2021/07/15/lc-domino.jpg" style="height: 195px; width: 362px;" />

给定整数 n ，返回可以平铺&nbsp;<code>2 x n</code> 的面板的方法的数量。返回对&nbsp;<code>109&nbsp;+ 7</code>&nbsp;取模&nbsp;的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

&nbsp;

示例 1:

<img src="https://assets.leetcode.com/uploads/2021/07/15/lc-domino1.jpg" style="height: 226px; width: 500px;" />

<pre>
输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。
</pre>

示例 2:

<pre>
输入: n = 1
输出: 1
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>