推 JIWP: 大師，我只觀察到dp[i]=dp[i-1]*2+dp[i-3] 05/05 14:17
→ yam276: 我看解說的 我DP很爛 05/05 14:20
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
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1746425439.A.546.html
※ 編輯: yam276 (60.248.143.163 臺灣), 05/05/2025 14:12:31