[LeetCode]Domino and Tromino Tiling

这道题很明显是要考虑状态之间的转移，应该是要用DP解的，问题是我们如何量化不同的状态。第一种容易想到的是用第一行和第二行(从下到上)tile的数量来表示，比如dp[i][j]表示第一行前i个填满了，第二行前j个填满了的状态。然后我们再考虑状态转移方程，比如i == j的时候，我们可以放任意一个tile:

• 右边放上I
• 第一层放I90(顺时针旋转90度)
• 第二层放I90
• 右边放L
• 右边放L90(顺时针旋转90度)

我们可以根据这些推导出转移方程。但是这里显然我们还是有很多不必要的状态的计算。比如dp[2][7]本质上和dp[6][7]是一样的，因为第二层我们只能插入I90，没有别的选择。而且空间也浪费。我们需要在这个基础上接着优化。

既然当i和j之间的大于等于2的时候，tile数较小的那一行我们是别无选择的话，我们就考虑当前最右端没有填满的列和下一列即可。当前列有四个状态：

1. 没有任何一个格子被填满，方法数记为dp[0]
2. 只有第一行(从下到上)被填满，方法数记为dp[1]
3. 只有第二行被填满，方法数记为dp[2]
4. 两行都被填满，方法数记为dp[3]

我们可以推导出状态转移的公式的：

1. 当前处于状态1
1. 插入I，下一列变为状态1
2. 上下两行插入两个I90，下一列变为状态4
3. 插入L，下一列变为状态2
4. 插入L90，下一列变为状态3
2. 当前处于状态2
1. 第二行插入I90，下一列变为状态3
2. 插入L180，下一列变为状态4
3. 当前处于状态3
1. 第一行插入I90，下一列变为状态2
2. 插入L270，下一列变为状态4
4. 当前处于状态4，我们无法当前列进行操作，下一列变为状态1

所以对应的状态转移方程为, newDp[i]表示下一列处于状态i的方法数：

• newDp[0] = dp[0] + dp[3]
• newDp[1] = dp[0] + dp[2]
• newDp[2] = dp[0] + dp[1]
• newDp[3] = dp[0] + dp[1] + dp[2]

我们根据转移方程写代码解。时间复杂度O(n)，常数空间，代码如下：

另一种方法很有意思，由于我们可以把状态转移方程写作矩阵的乘法。初始矩阵为A = {1, 0, 0, 0}，即初始状态，转移矩阵为T = {{1, 1, 1, 1}, {0, 0, 1, 1}, {0, 1, 0, 1}, {1, 0, 0, 0}}，相乘即为上面的状态转移方程，那么中的状态为A * T^n。求T的n次方我们可以用矩阵快速幂的方法，具体请参考这篇文章。时间复杂度O(log n)，快速幂的时间复杂度，常数空间。代码如下：