LeetCode 790 - Domino and Tromino Tiling


https://leetcode.com/problems/domino-and-tromino-tiling/description/
We have two types of tiles: a 2x1 domino shape, and an "L" tromino shape. These shapes may be rotated.
XX  <- domino

XX  <- "L" tromino
X
Given N, how many ways are there to tile a 2 x N board? Return your answer 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:
Input: 3
Output: 5
Explanation: 
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
Note:
  • N  will be in range [1, 1000].
https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116664/Schematic-explanation-of-two-equivalent-DP-recurrence-formula
First, how many types of tiles do we have (including rotation)?
The answer is six: two types from domino and four types from trimino. I label them as follows:
type 1: imagerepresenting vertical domino
type 2: imagerepresenting horizontal domino
type 3: imagerepresenting L-shaped trimino
type 4: imagerepresenting Gamma-shaped trimino
type 5: image representing mirrored-L-shaped trimino
type 6: imagerepresenting mirrored-Gamma-shaped trimino
Now let's define T(N) as the number of ways tiling the 2 x N board. To obtain the recurrence relations for T(N), we shall consider the very last tile in the 2 x Nboard (this is the tile which occupies at least one of the two grids at index N and completes the 2 x N board). So what type can it be?
Immediately we can rule out type 3 and 4, because they will never complete the board, thus cannot be the last tile. So we end up with four choices for the last tile:
  1. The last tile is of type 1: in this case, the rest tiles will fill up the 2 x (N-1) board, then by definition, the number of ways for this case will be T(N-1).
  2. The last tile is of type 2: in this case, the second to last tile must also be of type 2 (so they together fill up the last 2 x 2 region), and the rest tiles will fill up the 2 x (N-2) board, again by definition, the number of ways for this case will be T(N-2).
  3. The last tile is of type 5: in this case, the rest tiles must fill up the 2 x (N-1) board except for the lower grid at index N-1, like this shape: image. Our definition of T(N) does not cover this case, so we have to generalize it and define T_up(N) as the the number of ways to fill a 2 x N board except for the last lower grid. Then the number of ways for this case will be T_up(N-1).
  4. The last tile is of type 6: in this case, the rest tiles must fill up the 2 x (N-1) board except for the upper grid at index N-1, like this shape: image. Our definition of T(N) does not cover this case either, so we define T_down(N) as the the number of ways to fill a 2 x N board except for the last upper grid. Then the number of ways for this case will be T_down(N-1).
It's easy to show that the four cases will not overlap with each other (because at least the last tile will be different), and since the last tile must be one of the four cases, we conclude:
T(N) = T(N-1) + T(N-2) + T_up(N-1) + T_down(N-1)
This looks like a recurrence formula, except that we do not know T_up(N) and T_down(N) yet. To figure them out, we can follow exactly the same analyses above by considering the very last tile for each of them.
Take T_up(N) as an example. We want to fill up a board shape like this: image. What could the type of the very last tile be? The answer is: type 2(horizontal domino) and type 4 (Gamma-shaped trimino). For the former, the rest of tiles will fill up a 2 x (N-1) board except for the last upper grid, and by definition, there are T_down(N-1) ways to do this. For the latter, the rest tiles will fill up a 2 x (N-2) board completely, and by definition, there are T(N-2) ways to do so. So we conclude:
T_up(N) = T_down(N-1) + T(N-2)
Similarly we can obtain:
T_down(N) = T_up(N-1) + T(N-2)
And, there you go, we have found the recurrence relations for T(N), T_up(N), T_down(N):
T(N) = T(N-1) + T(N-2) + T_up(N-1) + T_down(N-1)
T_up(N) = T_down(N-1) + T(N-2)
T_down(N) = T_up(N-1) + T(N-2)
The termination conditions are as follows:
For N = 0, we have T(0) = 1, T_up(0) = T_down(0) = 0;
For N = 1, we have T(1) = 1, T_up(1) = T_down(1) = 0.
Now it is straightforward to write the O(N) space solution. However, if you notice that T(N), T_up(N), T_down(N) are only related to those at indices N-1 and N-2, the space can be cut to O(1). Here is a quick implementation in Java:
private static final int MOD = 1_000_000_007;
    
public int numTilings(int N) {
    int T_prepre = 1, T_pre = 1;
    int T_up_pre = 0, T_down_pre = 0;
        
    for (int n = 2; n <= N; n++) {
        int T_cur = (int)((0L + T_prepre + T_pre + T_up_pre + T_down_pre) % MOD);
        int T_up_cur = (T_prepre + T_down_pre) % MOD;
        int T_down_cur = (T_prepre + T_up_pre) % MOD;
            
        T_prepre = T_pre;
        T_pre = T_cur;
            
        T_up_pre = T_up_cur;
        T_down_pre = T_down_cur;
    }
        
    return T_pre;
}

Wait..., we are not done yet. It turns out that the recurrence relations for T(N), T_up(N), T_down(N) can be combined into one. To see how, first note that we have:
T(N) = T(N-1) + T(N-2) + T_up(N-1) + T_down(N-1)
T_up(N-1) = T_down(N-2) + T(N-3)
T_down(N-1) = T_up(N-2) + T(N-3)
Now plug the second and third equations into the first one, we get:
T(N) = T(N-1) + T(N-2) + T_down(N-2) + T(N-3) + T_up(N-2) + T(N-3)
which can be regrouped as:
T(N) = T(N-1) + T(N-3) + [T(N-2) + T(N-3) + T_up(N-2) + T_down(N-2)]
Now if you recognize the part in square brakets which is simply T(N-1), we arrive at:
T(N) = 2 * T(N-1) + T(N-3).
I would refer you to this post shared by zhengkaiwei for more explanations of the meaning of this formula. Anyway, the following is the O(N) time and O(1) space based on this formula, where I used p3, p2, p1 to denote T(N-3), T(N-2), T(N-1) respectively, and initialize them to -1, 0 and 1 to account for correct recurrence values.
private static final int MOD = 1_000_000_007;
    
public int numTilings(int N) {
    int p3 = -1, p2 = 0, p1 = 1;
        
    for (int n = 1; n <= N; n++) {
        int cur = (int)((p1 * 2L + p3) % MOD);
        p3 = p2;
        p2 = p1;
        p1 = cur;
    }
        
    return p1;
}
https://github.com/cherryljr/LeetCode/blob/master/Domino%20and%20Tromino%20Tiling.java
 * Approach: Sequence DP
 * 这类题刚刚开始看并没有什么想法，需要写出初始的几个状态，然后试着递推看看。
 * 通常就能发现规律，然后根据这个写出 递推方程（动态规划方程）即可。
 *
 * dp[i][0]:表示到 ith 列，全部完全铺满的方案个数
 * dp[i][1]:表示到 ith 列，剩余 左上角/右小角 一个格子未铺满的方案个数。
 * 则当前状态依赖于：
 *  dp[i-2][0]: 还差 两列 完全铺满，则再加两个横条便能够得到当前状态;
 *  dp[i-1][0]: 还差 一列 完全铺满，则再加一个竖条便能够得到当前状态；
 *  2 * dp[i-1][1]: 还差一个 L 完全铺满（缺的位置可以是 右上角 或者是 右下角），
 *  则再加一个 L 便可以得到当前状态。
 *
 * 类似的问题还有：
 * Dyeing Problem:
 *  https://github.com/cherryljr/LintCode/blob/master/Dyeing%20Problem.java
 * Find the Derangement of An Array:
 *  https://github.com/cherryljr/LintCode/blob/master/Find%20the%20Derangement%20of%20An%20Array.java
 *
 * 参考资料：https://www.youtube.com/watch?v=S-fUTfqrdq8
    private static final int MOD = 1000000007;

    public int numTilings(int N) {
        long[][] dp = new long[N + 1][2];
        dp[0][0] = 1;
        dp[1][0] = 1;
        for (int i = 2; i <= N; i++) {
         // 因为这边使用了 long 所以在相加时不担心溢出，如果是 int 的话，运算过程中也需要取模才行
            dp[i][0] = (dp[i - 2][0] + dp[i - 1][0] + 2 * dp[i - 1][1]) % MOD;
            dp[i][1] = (dp[i - 2][0] + dp[i - 1][1]) % MOD;
        }
        return (int)dp[N][0];
    }

http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-790-domino-and-tromino-tiling/
dp[i][0]: ways to cover i cols, both rows of i-th col are covered
dp[i][1]:  ways to cover i cols, only top row of i-th col is covered
dp[i][2]:  ways to cover i cols, only bottom row of i-th col is covered
Solution 1: DP
Time complexity: O(N)
Space complexity: O(N)
  int numTilings(int N) {
    constexpr int kMod = 1000000007;
    vector<vector<long>> dp(N + 1, vector<long>(3, 0));    
    dp[0][0] = dp[1][0] = 1;
    for (int i = 2; i <= N; ++i) {
      dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % kMod;
      dp[i][1] = (dp[i - 2][0] + dp[i - 1][2]) % kMod;
      dp[i][2] = (dp[i - 2][0] + dp[i - 1][1]) % kMod;
    }
    
    return dp[N][0];
  }

Since dp[i][1] always equals to dp[i][2], we can simplify a bit.
  int numTilings(int N) {
    constexpr int kMod = 1000000007;
    vector<vector<long>> dp(N + 1, vector<long>(2, 0));    
    dp[0][0] = dp[1][0] = 1;
    for (int i = 2; i <= N; ++i) {
      dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1]) % kMod;
      dp[i][1] = (dp[i - 2][0] + dp[i - 1][1]) % kMod;      
    }
    
    return dp[N][0];
  }
https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116581/Detail-and-explanation-of-O(n)-solution-why-dpn2*dn-1%2Bdpn-3
image
sorry my handwriting is ugly
dp[n]=dp[n-1]+dp[n-2]+ 2*(dp[n-3]+...+d[0])
=dp[n-1]+dp[n-2]+dp[n-3]+dp[n-3]+2*(dp[n-4]+...+d[0])
=dp[n-1]+dp[n-3]+(dp[n-2]+dp[n-3]+2*(dp[n-4]+...+d[0]))
=dp[n-1]+dp[n-3]+dp[n-1]
=2*dp[n-1]+dp[n-3]
http://www.cnblogs.com/pk28/p/8470177.html
思路：分3个状态，第i列上边凸出，下边凸出，和平的。如图，那么状态转换如图中公式。
https://blog.csdn.net/Faldict/article/details/79392996
It is not difficult to think of dynamic programming after reading the problem. However, the design of the recurrent formula is the key points. Initially, we set dp[0] = dp[1] = 1 and dp[2] = 2 for convenience. When n > 3, we cover the tiles square by square. There are three cases:
  1. Add an “XX” tile vertically and step one square forward.
  2. Add two “XX” tile horizontally and step two square forward.
  3. Add a combination of two trominos and X - 3 dominos and step X square forward.
Thus we get a recurrent formula:
dp[n] = dp[n-1] + dp[n-2] + 2 * \sum_{i=0}^{n-3} dp[i]
    

  • 1
    •
To speed up the calculation, we use an array to store the data. Notice that the answer should modulo 1e9+7. 
int numTilings(int N) { int md = 1e9+7; long long tiles[1005]; tiles[0] = 1; tiles[1] = 1; tiles[2] = 2; for (int i=3; i <= N; i++) { tiles[i] = tiles[i-1] + tiles[i-2]; for (int j=0; j <= i-3; j++) { tiles[i] += 2 * tiles[j]; tiles[i] %= md; } } return tiles[N]; }


And the formula can be simplified into the form as below, and the proof is omitted:
dp[n] = 2 * dp[n-1] + dp[n-3]
https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116581/Detail-and-explanation-of-O(n)-solution-why-dpn2*dn-1+dpn-3
dp[n]=dp[n-1]+dp[n-2]+ 2*(dp[n-3]+...+d[0])
=dp[n-1]+dp[n-2]+dp[n-3]+dp[n-3]+2*(dp[n-4]+...+d[0])
=dp[n-1]+dp[n-3]+(dp[n-2]+dp[n-3]+2*(dp[n-4]+...+d[0]))
=dp[n-1]+dp[n-3]+dp[n-1]
=2*dp[n-1]+dp[n-3]
 int numTilings(int N) {
    int md=1e9;
    md+=7;
    vector<long long> v(1001,0);
    v[1]=1;
    v[2]=2;
    v[3]=5;
    if(N<=3)
        return v[N];
    for(int i=4;i<=N;++i){
        v[i]=2*v[i-1]+v[i-3]; 
        v[i]%=md;
    }
    return v[N];
    
}

http://bookshadow.com/weblog/2018/02/25/leetcode-domino-and-tromino-tiling/
dp[x][y]表示长度（两行的最小值）为x，末尾形状为y的拼接方法个数
y有三种可能：
0表示末尾没有多余部分

1表示第一行多出1个单元格

2表示第二行多出1个单元格
状态转移方程：
dp[x][0] = (dp[x - 1][0] + sum(dp[x - 2])) % MOD   1个竖条， 2个横条，L7， rotate(L7)

dp[x][1] = (dp[x - 1][0] + dp[x - 1][2]) % MOD    rotate(L)，L + 第一行横条

dp[x][2] = (dp[x - 1][0] + dp[x - 1][1]) % MOD    L，rotate(L) + 第二行横条
def numTilings(self, N): """ :type N: int :rtype: int """ MOD = 10**9 + 7 dp = [[0] * 3 for x in range(N + 10)] dp[0] = [1, 0, 0] dp[1] = [1, 1, 1] for x in range(2, N + 1): dp[x][0] = (dp[x - 1][0] + sum(dp[x - 2])) % MOD dp[x][1] = (dp[x - 1][0] + dp[x - 1][2]) % MOD dp[x][2] = (dp[x - 1][0] + dp[x - 1][1]) % MOD return dp[N][0]
Another way to think about this problem
define: dp[i] ways to completely covert the i*2 board.
  int numTilings(int N) {
    constexpr int kMod = 1000000007;
    vector<long> dp(N + 1, 1);
    dp[2] = 2;
    for (int i = 3; i <= N; ++i)
      dp[i] = (dp[i - 3] + dp[i - 1] * 2) % kMod;
    return dp[N];
  }

https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116622/O(logN)-time-O(1)-space-linear-algebraic-algorithm-(in-python)


lc 790 follow up poj 2446
第二轮：
中国大哥
给一个2*n的board，每个格子有两种情况，为空或者被block了。现在有大小为1*2的多米诺骨牌，问这个board最多能放多少个骨牌

思路：
动态规划
dp[i] 表示[0, i] 的最多骨牌
case 1: i列上没有block
dp[i] = dp[i - 1] + 1;
case 1.1: 如果dp[i-1]也没有block
dp[i] = max(dp[i], dp[i-2] + 2)
case 2: i列上有一个block
dp[i] = dp[i-1]
case 2.1: 如果i-1列上没有block or i-1上有一个block在同侧
dp[i] = max(dp[i], dp[i-2] + 1)
case 3: i列上有两个block
dp[i] = dp[i - 1]

followup: board的size为m * n

这道题面经是我贡献的，为了不让大家觉得这道题难得过分以及花太多时间在这道题上，我想具体说明一下。根据面试时面试官给我的信息，这道题能够用greedy或者dp做出2*n的情况就已经非常不错了，如果你能答出m*n的思路当然非常加分，但是即使不知道也完全没关系，更不用要求能写出代码了。我自己在面的时候也只是在面试官的帮助下写出了dp，followup完全是面试官自问自答lol，最后还是过了HC。所以希望大家不用太panic，时间有限的情况下可以不用太在意followup


at
Labels: , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts