LeetCode 75
Domino and Tromino Tiling
- Problem
- LC 790
- Topic
- DP 1D
- File
- official75_LC790DominoAndTrominoTiling.java
- Path
- pkg5leetcode/official75/official75_LC790DominoAndTrominoTiling.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC790DominoAndTrominoTiling.java
- Approach
- DP states full/partial row coverage mod 1e9+7.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Domino and Tromino Tiling | LC 7905 * APPROACH: DP states full/partial row coverage mod 1e9+7.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class official75_LC790DominoAndTrominoTiling {9 static int numTilings(int n) {10 final int MOD = 1_000_000_007;11 if (n < 3) return n;12 long[] dp = new long[n + 1];13 dp[1] = 1;14 dp[2] = 2;15 dp[3] = 5;16 for (int i = 4; i <= n; i++)17 dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD;18 return (int) dp[n];19 }20 21 public static void main(String[] args) {22 check(numTilings(3) == 5, "case1");23 check(numTilings(4) == 11, "case2");24 System.out.println("all tests passed");25 }26 27 static void check(boolean cond, String name) {28 if (!cond) throw new AssertionError("FAILED: " + name);29 System.out.println(" PASS " + name);30 }31}