790. Domino and Tromino Tiling
https://leetcode.com/problems/domino-and-tromino-tiling/
题意：
你有2x1跟L型的多米诺
能拼出几种2xn的矩阵
思路：
这题有一个简单版是只有2x1的多米诺来填满2xn矩阵
在简单版可以整理直的横的
n=1 直
n=2 直直 横
横
n=3 直直直 横直 直横
横 横
以n=3的情况会变成 dp[n] = dp[n-1] + dp[n-2]
因为第三个直横横是从n=1过来的其他则是从n=2延伸
整理之后会直接变成费波纳契数列
接着是本题
包含L多米诺比较复杂 因为有凸出来的模式
直接看我找到的影片的图
https://i.imgur.com/ryRR56z.png
这边用二维dp来处理
dp[i][0]代表填满 没凸出的情况
dp[i][1]代表凸出上面一格
dp[i][2]代表凸出下面一格
那首先dp[i][0]可以用上面的简单版处理
所以就是 dp[i-1][0] + dp[i-2][0]
dp[i][1]/dp[i][2] 则是有两种情况
都可以被一个L多米诺完整包覆
所以只要算出他们的数量加上去就好
这边计算凸出的组合有两种：
一种是已经凸出一格 加上一条横向的I型多米诺
一种则是上一轮完美包覆 所以加上一条L型多米诺
这两种都会形成新的凸出一格的组合：
dp[i][1] = dp[i-2][0] + dp[i-1][2]
完美包覆+L 凸出一格+横向I
dp[i][2] = dp[i-2][0] + dp[i-1][1]
完美包覆+L 凸出一格+横向I
整理到这边会发现 他们是一样的模式
所以其实计算其中一种*2就好了
因此最后可以依序整理出：
dp[i][0] = dp[i-1][0] + dp[i-2][0] + dp[i-1][1] + dp[i-1][2]
(简易版只有I的情况) + (突出上面+突出下面的情况)
简化后者 之后计算的时候不用再考虑dp[i][2]了 通通当成dp[i][1]
dp[i][0] = dp[i-1][0] + dp[i-2][0] + 2*dp[i-1][0]
最后求出的dp[n][0]就是答案
最后题目还有个要求说数字可能很大
所以要mod 1000000007
Code:
impl Solution {
pub fn num_tilings(n: i32) -> i32 {
const K_MOD: i64 = 1_000_000_007;
let mut dp = vec![vec![0i64; 2]; (n + 1) as usize];
dp[0][0] = 1;
dp[1][0] = 1;
for i in 2..=n {
let i = i as usize;
dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1]) % K_MOD;
dp[i][1] = dp[i - 2][0] + dp[i - 1][1];
}
dp[n as usize][0] as i32
}
}

大师，我只观察到dp[i]=dp[i-1]*2+dp[i-3]

我看解说的 我DP很烂