Re: [閒聊] 每日leetcode
※ 引述《yam276 (史萊哲林的優等生)》之銘言：
: 790. Domino and Tromino Tiling
: https://leetcode.com/problems/domino-and-tromino-tiling/
: 題意：
: 你有2x1跟L型的多米諾
: 能拚出幾種2xn的矩陣
我想到的解法是只用一維的dp，
具體思路是把每一次dp得到的數字都設為此時有幾種2*i的骨牌組合，
並設2*0為1種，
不過時間複雜度就會高一點
例如2*1矩形有1種組合，
2*2矩形可以是2*1矩形再加上1個豎直擺放的長方形骨牌，
或從頭開始擺2個橫向擺放的長方形骨牌，
結果是1+1=2種
2*3矩形則是除2*2矩形加1個直骨牌與2*1矩形加2個橫骨牌之外，
還可以從頭開始擺2個L形骨牌，有2種擺法
結果是2+2+1=5種
歸納結果，
如果當前要組2*i的矩形，
在i>2的情況下，
其組合總數是dp[0:i-2] * 2 + dp[i-2] + dp[i-1]種
--
Python Code:
class Solution:
def numTilings(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
MOD = 1_000_000_007
for i in range(1, n + 1):
dp[i] = ((sum(dp[0:i-2]) * 2 if i > 2 else 0) + dp[i-2] + dp[i-1])
% MOD
return dp[-1]
: 思路：
: 這題有一個簡單版是只有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), 來自: 1.163.171.25 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1746461955.A.5B4.html
→
05/06 00:27,
7月前
, 1F
05/06 00:27, 1F
→
05/06 00:47,
7月前
, 2F
05/06 00:47, 2F
推
05/06 00:55,
7月前
, 3F
05/06 00:55, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 1417 之 1548 篇)：