LeetCode Solutions
790. Domino and Tromino Tiling
Time: $O(N)$ Space: $O(N)$
class Solution {
public:
int numTilings(int N) {
constexpr int kMod = 1'000'000'007;
vector<long> dp(1001, 0);
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for (int i = 4; i <= N; ++i)
dp[i] = (2 * dp[i - 1] + dp[i - 3]) % kMod;
return dp[N];
}
};
class Solution {
public int numTilings(int N) {
final int kMod = 1_000_000_007;
long[] dp = new long[1001];
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for (int i = 4; i <= N; ++i)
dp[i] = (2 * dp[i - 1] + dp[i - 3]) % kMod;
return (int) dp[N];
}
}
class Solution:
def numTilings(self, N: int) -> int:
kMod = 1_000_000_007
dp = [0, 1, 2, 5] + [0] * 997
for i in range(4, N + 1):
dp[i] = 2 * dp[i - 1] + dp[i - 3]
return dp[N] % kMod