790. Domino and Tromino Tiling
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
Dynamic Programming
一、題目
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 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 1:
- Input: n = 3
- Output: 5
- Explanation: The five different ways are show above.
Example 2:
- Input: n = 1
- Output: 1
Constraints:
1 <= n <= 1000
二、分析
- 直覺上列出前 5 個解為：
1,2,5,11,24，若用觀察法猜公式可以猜到dp[n] = 2*dp[n-1] + dp[n-3]，便可以快速解出答案。 - 以下為網友的分析
也就是說，
\( \text{dp[n] = dp[n-1]+dp[n-2]+2(dp[n-3]+…+dp[0])}\\ \text{dp[n-1] = dp[n-2]+dp[n-3]+2(dp[n-4]+…+dp[0])}\\ \text{dp[n]=2}\times\text{dp[n-1]+dp[n-3]} \)
三、解題
1. DP
- Time complexity: \(O(n)\)
- Space complexity: \(O(n)\)
int numTilings(int n) {
int MOD = (int)1e9+7;
if (n <= 2) return n;
if (n == 3) return 5;
vector<long long int> dp(n+1);
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for (int i = 4; i <= n; i++) {
dp[i] = (dp[i-1]*2 + dp[i-3]) % MOD;
}
return (int)dp[n];
}