Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/12/24 19:35)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串151/719 (看更多)

※ 引述《pandix (麵包屌)》之銘言： : 790. Domino and Tromino Tiling : 你有兩種骨牌，一種是兩個方塊的I型，一種是三個方塊的L型 : https://assets.leetcode.com/uploads/2021/07/15/lc-domino.jpg

: 請你算出用這兩種骨牌組成 2*n 的盤面總共有幾種擺列方法 : Example 1: : Input: n = 3 : Output: 5 : 直接上圖: https://assets.leetcode.com/uploads/2021/07/15/lc-domino1.jpg

: Example 2: : Input: n = 1 : Output: 1 思路： 1.觀察一下Example可以發現後面的狀態可以藉由前面的狀態增加骨牌來得到，所以可以考慮用動態規劃。 2.定義 dp[i][j] 為第i列的所有骨牌組合可能，j表示第i列的四種狀態，如下所示紅色部分為第i-1列： 0:第i列什麼都沒有 ▉ ▉ 1:第i列第一行有方塊 ▉▉ ▉ 2:第i列第二行有方塊 ▉ ▉▉ 3:第i列被填滿 ▉▉ ▉▉ 3.歸納出所有狀態的變化： (1)第i列什麼都沒有只可能由「上一輪已經被填滿了」轉變而成： i-1 ==> i ▉ ▉ ▉ ▉ 狀態轉移方程：dp[i][0] = dp[i - 1][3] (2)第i列第一行有方塊只有可能為下列兩種狀態轉變而成： * 第i列什麼都沒有加上一個size3的骨牌 i-2 i-1 i ▉ <- ▉▉ ▉ ▉ * 第i列第二行有方塊加上一個直的size2骨牌 i-2 i-1 i ▉ <- ▉▉ ▉ ▉ 狀態轉移方程：dp[i][1] = dp[i - 1][0] + dp[i - 1][2] (3)第i列第二行有方塊就只是上面的方向相反而已，概念一樣狀態轉移方程：dp[i][2] = dp[i - 1][0] + dp[i - 1][1] (4)第i列被填滿會有四種情況 *第i-1列沒方塊加上兩個size2骨牌 i-1 i <- ▉▉ ▉▉ *第i-1列第一行有方塊加上一個size3骨牌 i-1 i ▉ ▉ <- ▉▉ *第i-1列第二行有方塊加上一個size3骨牌 i-1 i <- ▉▉ ▉ ▉ *第i-1列被填滿加上一個size2骨牌 i-1 i ▉ <- ▉ ▉ ▉ 狀態轉移方程： dp[i][3] = dp[i][0] + dp[i][1] + dp[i][2] + di[i][3] 4.定義初值 dp[0][0] = 1 一開始的狀態就是i-1列沒任何方塊 dp[0][3] = 1 一開始什麼都沒有的時候放一個橫的就填滿了 5.因為數字很大，所以任意兩數做處理之後都要模1000000007（題目要求） 6.返回最後一輪填滿的表即可（dp[n - 1][3]） Java Code： --------------------------- class Solution { private int M = 1000000007; public int numTilings(int n) { if (n == 1) { return 1; } int[][] dp = new int[n][3]; dp[0][0] = 1; dp[0][3] = 1; for (int i = 1; i < n; i++) { dp[i][0] = dp[i - 1][3]; dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % M; dp[i][2] = (dp[i - 1][0] + dp[i - 1][2]) % M; dp[i][3] = (((dp[i - 1][0] + dp[i -1][1]) % M + dp[i - 1][2]) % M + dp[i - 1][3]) % M; } return dp[n - 1][3]; } } --------------------------- 這題我覺得頗難的想了一下午然後狀態1和2因為是鏡像所以可以合併在一起改成*2可以讓空間複雜度少一些 -- https://i.imgur.com/bFRiqA3.jpg