提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助文檔

目錄

729.多米諾和托米諾平鋪

動態規劃

代碼實現

---

最近看到的一道經典的動態規劃題，做個筆記記錄一下（題目來自leetcode）

---

729.多米諾和托米諾平鋪

有兩種形狀的瓷磚：一種是?2 x 1?的多米諾形，另一種是形如?"L" 的托米諾形。兩種形狀都可以旋轉。

給定整數 n ，返回可以平鋪?2 x n 的面板的方法的數量。返回對?109?+ 7?取模?的值。

平鋪指的是每個正方形都必須有瓷磚覆蓋。兩個平鋪不同，當且僅當面板上有四個方向上的相鄰單元中的兩個，使得恰好有一個平鋪有一個瓷磚占據兩個正方形。

示例1：

輸入: n = 3 輸出: 5 解釋: 五種不同的方法如上所示。

---

動態規劃

默認平鋪方式，在第i列前的正方形都被瓷磚所覆蓋，在第i列之后的正方形都沒有被瓷磚所覆蓋(i從1開始計數)。那么第i列存在的所有情況如下

• 一個正方形都沒有被覆蓋，記為狀態 0；

列數					第i列

• 只有上方的正方形被覆蓋，記為狀態 1；

列數					第i列

• 只有下方的正方形被覆蓋，記為狀態 2；

列數					第i列

• 上下兩個正方形都被覆蓋，記為狀態 3。

列數					第i列

我們默認第0列正方形都被覆蓋，則初始化 dp[0][0]=0,dp[0][1]=0,dp[0][2]=0,dp[0][3]=1

對應的狀態轉移方程為

• dp[i][0] = dp[i - 1][3]
• dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
• dp[i][2] = dp[i - 1][0] + dp[i - 1][1]
• dp[i][3] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]

最后返回dp[n][3]

---

代碼實現

class Solution {static final int MOD = 1000000007;public int numTilings(int n) {int[][] dp = new int[n + 1][4];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][2]) % MOD;dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;dp[i][3] = (((dp[i - 1][0] + dp[i - 1][1]) % MOD + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD;}return dp[n][3];} }

總結

以上是生活随笔為你收集整理的多米诺和托米诺平铺(动态规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。