🥈

Domino and Tromino Tiling

Created

2021/12/10 05:00

문제 번호

790

카테고리

Dynamic Programming

Domino and Tromino Tiling - LeetCode

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes. Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo .

https://leetcode.com/problems/domino-and-tromino-tiling/

Code

제출 날짜	시간	메모리
2021/12/10	0 ms	2.1 MB

// 790. Domino and Tromino Tiling
//
// https://leetcode.com/problems/domino-and-tromino-tiling/
//
// Tiling can be done with Domino and Tromino
// Finding the number of cases to tile with the size n
const mod = 1e9 + 7
// Size Bigger than 3
// Using Domino -> i - 1 case & i - 2 case
// Using Tromino -> (i - 3 ... 0) * 2
// dp[i] = dp[i-1] + dp[i-2] + sigma(0 to i - 3) * 2
// dp[i] = dp[i-1] + dp[i-3] + dp[i-1]
func numTilings(n int) int {
if n < 3 {
return n
}
dp := make([]int, n+1)
dp[0] = 1
dp[1] = 1
dp[2] = 2
dp[3] = 5
for i := 4; i <= n; i++ {
dp[i] = (2*dp[i-1] + dp[i-3]) % mod
}
return dp[n]
}
Go