ðŸ¥ˆ

# Domino and Tromino Tiling

Created
2021/12/10 05:00
ë¬¸ì œ ë²ˆí˜¸
790
ì¹´í…Œê³ ë¦¬
Dynamic Programming

### Code

 .css-15tnwsa{max-width:100%;width:100%;white-space:pre-wrap;word-break:break-word;padding:7px 9px;background-color:transparent;font-size:14px;line-height:20px;min-height:1em;}.css-15tnwsa:empty::after{content:" ";}ì œì¶œ ë‚ ì§œ ì‹œê°„ ë©”ëª¨ë¦¬ 2021/12/10 0 ms 2.1 MB
// 790. Domino and Tromino Tiling // // https://leetcode.com/problems/domino-and-tromino-tiling/ // // Tiling can be done with Domino and Tromino // Finding the number of cases to tile with the size n const mod = 1e9 + 7 // Size Bigger than 3 // Using Domino -> i - 1 case & i - 2 case // Using Tromino -> (i - 3 ... 0) * 2 // dp[i] = dp[i-1] + dp[i-2] + sigma(0 to i - 3) * 2 // dp[i] = dp[i-1] + dp[i-3] + dp[i-1] func numTilings(n int) int { if n < 3 { return n } dp := make([]int, n+1) dp[0] = 1 dp[1] = 1 dp[2] = 2 dp[3] = 5 for i := 4; i <= n; i++ { dp[i] = (2*dp[i-1] + dp[i-3]) % mod } return dp[n] }
Go