LeetCode--790. 多米诺和托米诺平铺

790. 多米诺和托米诺平铺

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 10^9 + 7 取模 的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

---

很像一个背包问题，也很像蒙德里安的梦想那道题，但是没有那么麻烦，无需状态压缩，只需要一维的状态转移即可。

我们为初始状态赋值，因为我们必须要根据三种状态来进行 dp 。

n = 1 时，组合数为 1， n = 2 时， 组合数为 2， n = 3 时， 组合数为 5。

这样，初始状态就得到了，随后我们需要根据这三个初始状态进行 dp ，当我们需要求得 n * 2 的面板的组合数，我们可以知道，它的组合数自然是根据前面的状态计算出来的，比如， n = n - 3 的时候，通过加入 2 * 3 的面板，我们可以得到一些组合，当 n = n - 1 的时候，我们可以通过加入 2 * 1 的块，来得到部分组合，当然，我们的 n = n - 2 的情况是不需要考虑的，因为他已经包含在了 n = n - 1的情况里面，只需要乘以 2 即可。

func numTilings(n int) int {
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    if n == 3 {
        return 5
    }
    mod := 1000000007
    f := make([]int, n + 1)
    f[1], f[2], f[3] = 1, 2, 5
    for i := 4; i <= n; i ++ {
        f[i] = (2 * f[i - 1] + f[i - 3]) % mod
    }
    return f[n]
}