DominoAndTrominoTiling [source code]
public class DominoAndTrominoTiling {
static
/******************************************************************************/
class Solution {
final int MOD = 1_000_000_007;
public int numTilings(int N) {
long[] D = new long[N + 1], T = new long[N + 1];
D[0] = 1;
D[1] = 1;
T[0] = 1;
for (int i = 2; i <= N; i++) {
D[i] = (D[i - 1] + D[i - 2] + 2 * (T[i - 1])) % MOD;
T[i] = (T[i - 1] + D[i - 2]) % MOD;
}
return (int) D[N];
}
}
/******************************************************************************/
public static void main(String[] args) {
DominoAndTrominoTiling.Solution tester = new DominoAndTrominoTiling.Solution();
int[] inputs = {
4, 11,
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int N = inputs[2 * i], ans = inputs[2 * i + 1], output = tester.numTilings (N);
System.out.printf ("%d -> %s, expected: %d\n",
N, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
比我想象中的难, contest结束的时候这题的AC rate只有400/2K;
这个是contest看来的一个;
class Solution {
public:
int numTilings(int N) {
int f[1005], i, j, P = 1000000007;
f[0] = f[1] = 1;
for (i = 2; i <= N; i++) {
f[i] = f[i - 1] + f[i - 2];
if (f[i] >= P) f[i] -= P;
for (j = 3; j <= i; j++) f[i] = (f[i] + 2 LL * f[i - j]) % P;
}
return f[N];
}
};
这个好像不是很看得懂; 用[j]的和[i-j]的来组合, 这个是看得懂的, 但是你怎么知道[i-j]的一定要乘2呢?
后来好像看懂了; 你用长度为j的和长度为i-j的组合, 实际上组合的时候, 就是有一个相对上下对换位置的对称性造成的2倍. 就比如你先想想1..j这些, 这些是不会动的, 因为这些当时在算[j]的时候, 已经考虑过对称性了. 你现在从[i-j]的结果拿出来, 接在[j]后面, 这个接的时候, 就可以加一个上下对调的操作; 因为虽然[i-j]自己当时计算的时候是考虑过了这个i-j长度以内的对称性的, 但是因为现在是接在1..j后面了, 所以这两者之间的大的相对上下关系, 并没有考虑;
理解了之后, 不得不说这个算法虽然复杂度不是最理想的, 但是确实是最好理解的;
TODO:
2018-02-27 12:07:25 到目前为止, 还是看不懂editorial的做法; 给awice留言了也不知道会不会回;
上面的代码是mutual recursion的做法, 我认为这题这个解法是最有学习意义的;
editorial
Approach #1: Dynamic Programming [Accepted]
Intuition
Let dp[state] be the previous number of ways to fill i columns where the i-th row of the last column is filled if the i-th bit of state is 1.
In particular, dp[0] will be the number of ways to fill i columns where the last column has nothing filled; dp[1] will be the number of ways with the square in the last row filled; dp[2] will be the number of ways with the square in the first row filled; and dp[3] will be the number of ways with the squares in both rows filled.
From there, we only have to accurately record the transitions.
Algorithm
If in the future we have:
- 0 rows filled - it could have come from either:
- having 0 rows filled and a vertical domino, or
- both rows filled and nothing.
- last row filled - it could have come from either:
- having 0 rows filled and an L shaped tromino, or
- having top row filled and a horizontal domino
- first row filled - case is symmetric to the 'last row filled' case
- both rows filled - could have come from either:
- having 0 rows filled and two horizontal dominos, or
- having 1 row filled and an L shaped tromino (two cases.)
After writing the recurrence correctly, the solution follows.
这里解释的已经很好了, 配合这个应该不难理解:
上面这个图有点问题, 比如最后一行, 两个domino那个应该是horizontal;
class Solution {
public int numTilings(int N) {
int MOD = 1_000_000_007;
long[] dp = new long[]{1, 0, 0, 0};
for (int i = 0; i < N; ++i) {
long[] ndp = new long[4];
ndp[0b00] = (dp[0b00] + dp[0b11]) % MOD;
ndp[0b01] = (dp[0b00] + dp[0b10]) % MOD;
ndp[0b10] = (dp[0b00] + dp[0b01]) % MOD;
ndp[0b11] = (dp[0b00] + dp[0b01] + dp[0b10]) % MOD;
dp = ndp;
}
return (int) dp[0];
}
}
这个算法给的复杂度是O(N). 上面那个contest的做法, 肯定不是O(N)的;
他这里i的循环是0..N-1, 实际上用1..N更好理解一些; 因为他优化了空间, 所以实际上循环里面i并没有调用, 最后就是一个计数器;
我上面那个图示好像不太对啊, 讲不通, 这个是下面评论里面的一个人给的图示:
他这个我仔细看了一下, 好像也不对? 比如他算11的时候, 之前的00用了两次是什么鬼? 好像是应该用两次的; 那为什么awice的代码不需要两次呢;
但是这个人, 你看他01=01+11, 这个就跟awice的解释完全不对照了, 而且他自己这里画的本身也不一致;
awice的逻辑我是理解的, 但是我有两个疑点:
- 为什么要区分这么多种state(这里很明显state多加的dimension就是root, 也就是最后一个column是什么, 这个也是一个稍微有点复杂的root level decision).
- 为什么最后返回的是[0]?
另外, 看到这里, 发现awice还漏讲了一个东西, 所有这些state, 是只允许最后一个column有空缺的; 这样上面的计算才能讲的通;
想了一会儿, 想通了为什么最后返回[0], 因为他这里最开始的初始值其实对应的是end at [0], 所以比如N是4, 后面走4个循环, 那么最后dp代表的是end at [4], 这个当然是出界的, 但是这个时候的dp[0]就是我们要的;
为什么一定要算到出界为止? 我感觉如果在比如end at [3]对应的时候的直接返回dp[0b11]好像也可以? 没有去尝试, 不过回头一想好像不对, 因为假设我们给dp恢复第一维, 那么一开始给的是dp[0][..]所有的数值(end at N0), 然后最后返回的是dp[4][0]. 那么我的讨论就是, 直接返回dp[3][3]行不行? 但是这个时候你回头看你最后一个iteration是怎么算dp[4][0]的? 实际上中间还差了一个dp[3][0], 所以估计最后结果肯定是不对的; 这个也是带来了我的第一个问题, 为什么直接返回dp[3][3]不行? 感觉有点counter intuitive啊, 完全不好理解;
而且好像又多了一个问题:
- 为什么我的那种思路就不行呢? 到底逻辑上错过了什么?
后来看了discussion之后, 意识到我的算法的问题:
就是这种情况, 这种情况实际上是可以无限延伸的, 实际上, 整个N长度的都可以用这个方法来处理; 这也是为什么:
- discussion最优解要用一个累加到底的方法来计算[n];
- awice这里用的是一个更加general的方法, 通过增加dimension来提高这个模型的能力;
那么算是解决了很多问题了, 但是关于这里的:
- 算11的时候, 00为什么不乘2?
- 最后为什么返回[0]?
还是没有理解;
第一个问题理解了, 你仔细看他的解释, 他这里实际上是只包含了两个horizontal的domino, 而两个vertical的呢? 那个他没有包括, 因为他认为这个被包含在...被包含在哪里了? 突然想到, 计算11的公式里面, 为什么右边不包含11? 感觉定义里面应该还是有点东西我没有吃透;
这个是每一个iteration结束的时候的DP:
i:(0), dp: [[1, 1, 1, 1]]
i:(1), dp: [[2, 2, 2, 3]]
i:(2), dp: [[5, 4, 4, 6]]
i:(3), dp: [[11, 9, 9, 13]]
i:(4), dp: [[24, 20, 20, 29]]
Approach #2: Matrix Exponentiation
Intuition
The recurrence expressed in Approach #1 expressed states that transitioned to a linear combination of other states. Any time this happens, we can represent the entire transition as a matrix of those linear combinations. Then, the n-th power of this matrix represents the transition of n moves, and thus we can reduce the problem to a problem of matrix exponentiation.
algorithm: ...
好像就是一个bigger wheel的方法, 算法本身的核心思路是一样的, 就是把当中的一些component用更加fancy的方法做出来;
指数有一个技巧:
T^(2k) = T^k * T^kT^(2k+1) = T^(2k) * T
通过这个技巧来达到最后O(lgN)的复杂度;
class Solution {
int MOD = 1_000_000_007;
public int numTilings(int N) {
int[][] T = new int[][]{{1,0,0,1},{1,0,1,0},{1,1,0,0},{1,1,1,0}};
return matrixExpo(T, N)[0][0];
}
public int[][] matrixMult(int[][] A, int[][] B) {
int[][] ans = new int[A.length][A.length];
for (int i = 0; i < A.length; i++)
for (int j = 0; j < B[0].length; j++) {
long entry = 0;
for (int k = 0; k < B.length; k++)
entry += (long) A[i][k] * (long) B[k][j] % MOD;
ans[i][j] = (int) (entry % MOD);
}
return ans;
}
public int[][] matrixExpo(int[][] A, int pow) {
int[][] ans = new int[A.length][A.length];
for (int i = 0; i < A.length; i++) ans[i][i] = 1;
if (pow == 0) return ans;
if (pow == 1) return A;
if (pow % 2 == 1) return matrixMult(matrixExpo(A, pow-1), A);
int[][] B = matrixExpo(A, pow / 2);
return matrixMult(B, B);
}
}
这个东西要是给用numpy估计就更快了;
when N==0, we need return 0, but in dp , we need make dp[0]=1 for easy to construct formula
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]
=2dp[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];
}
我一开始那个想法居然是对的, 就是formula算错了;
另外你看他的草稿, 他这个formula的概念相当强. 这个在地里也是看到了, DP问题, 最后面试官最关心的, 就是你能不能把这个formula拿出来; 他面试你的时候手上攥着的就是这个formula, 对的上对不上, 很直观的事情;
另外他这个公式的推导是真的牛批, 非常敏锐的观察力;
他这个思路的核心其实就是跟上面contest看到的那个N^2的解法是类似的, 但是他观察的更加仔细, 他对这个公式发现可以化简, 这样就得到了O(N)的做法; 真的很聪明;
最重要的
你看看他这个草稿, 你有没有发现他实际上是在干什么? 他实际上就是自己手动把所有的几个例子全都列出来! 然后自己观察, 比如在dp[3]的时候, 直接看看能从dp[3]的等号右边, 找到上面几行哪个等号右边? 这个是有一点目标导向的做法, 但是非常有效, 前提是你要把这些东西都列出来, 只有看到了才容易发现这里的规律;
不对, 又看了一下, 他这个思考过程好像没有这么explicit;
回头想想我自己当时的思考过程, 其实基本完全是纯理论的, 就是完全从逻辑的角度去寻找formula; 这种一旦碰到稍微难一点的DP题目的时候是很难成功的; 我感觉这个还是因为我答案看多了的原因, 别人的现成解法, 逻辑清晰, 看多了之后以为这种题目的核心是直接上来就总结逻辑, 其实已经搞错方向了;
另外, 你看他的dp[4]这一行的最后两个, 这里我终于看出来我的思路的问题在哪里了; 说实话, 我这题根本就是连人逻辑(放在这题就是枚举出来实际的DP结果)都没有搞清楚, 最后能做出来就见鬼了;
对于这个解法(非常厉害), 最后一个要总结的东西就是, 当我们看到了:
dp[n] = dp[n - 1] + dp[n - 2] + 2 * (dp[n - 3] + ... + dp[0])
的时候, 怎么跟他这样发现, 最后肯定能把后面的归并呢?
也许是因为知道DP问题的formula本身就是一个recursive的, 所以当你有这么一个累加到底的式子的时候, 很大可能可以合并?
当然这个说法还是很抽象了, 具体来说的思路我也不知道;
可以这样理解, 如果你表达[n]需要累加到[0], 那么你表达比如比n小的一个, 比如[n-1], 很可能也要累加到[0], 那么中间肯定有一个可以总结代替的东西, 也就可以得到一个公式;
The idea is to have two functions numTilingsD that handles the number of ways of filling using Domio and numTilingsT that handles number of ways of filling using Tromino.
As this is a DP with recursive solution we have 2 caches cacheD and cacheT to store the corresponding solutions.If you open the images below in a new tab, they are a bit more readable.
def numTilings(self, N):
def numTilingsD(N):
if N in cacheD: return cacheD[N]
if N <= 2: return N if N > 0 else 1
cacheD[N] = (numTilingsD(N - 2) + numTilingsD(N - 1) + (2 * numTilingsT(N - 1))) % ((10**9) + 7)
return cacheD[N]
def numTilingsT(N):
if N in cacheT: return cacheT[N]
if N <= 2: return 0 if N == 1 else 1
cacheT[N] = (numTilingsD(N - 2) + numTilingsT(N - 1)) % ((10**9) + 7)
return cacheT[N]
cacheD, cacheT = {}, {}
return numTilingsD(N)
他这个思路还是很清晰的, 不过他这个图示到后面有点乱; 我自己重新画了一个;
这个好像还是第一次在LeetCode上面看到mutual recursion;
另外这个解法好像就是awice那个解法的原型; 等一会看看用这个解法的思路和定义能不能帮助理解awice的解法;
一个小的东西, 就是为什么T(2) = 1? 这些初始值你要搞清楚的; 当你讨论一个T(N)的时候, 往往还有另外一个T(N)跟这个T(N)是对称相等的, 但是你要清楚你的符号的定义, 你这里一个T(N), 对应的就是其中的一种情况; 所以比如长度为2的时候, 缺一门的填法实际上有两种, 但是每一个T(2)只代表其中的一种; 这个在上面的图示当中其实也是有展示的;
3 simple steps to solve this problem:
- Decide use dynamic programming.
- Find dp equation.
- Find initilization.
A[i] the number of tiling a 2N-1 board, B[i] the number of tiling a 2N board.
We can find this regular as .A[i] = B[i - 2] + A[i - 1]
B[i] = B[i - 1] + B[i - 2] + A[i - 1] * 2
I also initialize B[0] = B[1] = 1, A[0] = A[1] = 0Python:
def numTilings(self, N):
A = [0] * (N + 1)
B = [1, 1] + [0] * (N - 1)
for i in range(2, N + 1):
A[i] = (B[i - 2] + A[i - 1]) % int(1e9 + 7)
B[i] = (B[i - 1] + B[i - 2] + A[i - 1] * 2) % int(1e9 + 7)
return B[N]
跟上面类似的做法, 不过写的更加简练; 他的定义也更加的明确;
不过这个人比较奇怪的一点是他后来说, 你干脆直接观察序列, 然后直接就可以得到公式:
The answer will be a recursive sequence as follow: 1, 1, 2, 5, 11, 24, 53, 117, 258, 569, 1255
It grows at a speed about 2 times bigger each time.
If you write down this recursive sequence and do some calculations, you may find that:5 = 2 2 + 1
11 = 5 2 + 1
24 = 11 2 + 2
53 = 24 2 + 5
117 = 57 2 + 11
A[N] = A[N-1] 2 + A[N-3]Once you notice it, the rest work will be easy, even it may be hard to prove this regular.
这个被喷的挺厉害的:
but in a interview scenario, how do you know the answer sequence of the first several numbers?
反正正常的思路他应该还是有的;
底下有人对于这个公式给出了跟之前top vote看到类似的解释:
Hint for how to get the sequence:
A[N] can be get from A[N-1] by simply add
X
X
to the right of A[N-1],
A[N] can be get from A[N-2] by simply add
XX
YY
to the right of A[N-2] , Note that the method must be unique from those from A[N-1], thus the following tilling is not allowed:
XY
XY
cause it will be replicate to the cases from A[N-1] to A[N]
How about A[N-3] and all previous cases? There are always 2 unique ways to turn them into A[N] (add the following blocks to the right of A[N-i]):
- XX Y (from A[N-3])
X YY
XX YY (from A[N-4])
X ZZ Y
XX ZZ Y (from A[N-5])
X ZZ YY
XX ZZ YY (from A[N-6])
X ZZ ZZ Y
etc…- vertically flip case 1
Thus:
A[N] = A[N-1] + A[N-2] + 2 sum(A[:N-2])
if you plug A[N-1] = A[N-2] 2 +A[N-4] into A[N] = A[N-1] 2 + A[N-3] to replace one of the A[N-1], you will get:
A[N] = A[N-1] + A[N-2] 2 + A[N-3] + A[N-4]
and if you keep plugging in and replace one of the A[N-2], A[N-3], … etc
you will get the exact same expression:
A[N] = A[N-1] + A[N-2] + 2 * sum(A[:N-2])
关键点就是看到这个累加到底的思路;
一个用numpy的做法:
但是这个矩阵做法做的并没有awice的做法那么干净; 而且推导过程看起来很丰实, 实际上感觉有点不自然, 有点东拼西凑的感觉, 有时间再看了;
这题最后主流做法其实还是一个就是自己发现累加到底的那个做法, 一个就是mutual recursion的做法; awice的那个做法, 到现在为止还没有看懂;
Problem 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].
Difficulty:Medium
Total Accepted:388
Total Submissions:2K
Contributor:awice