資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學用 C++ 進行多米諾骨牌和多米諾骨牌三塊拼圖貼圖
假設我們有兩種型別的形狀，多米諾骨牌和多米諾骨牌三塊拼圖。它們可以像下面這樣旋轉：
在貼圖中，每個方塊都必須被圖塊覆蓋。如果棋盤上有兩個沿 4 個方向相鄰的單元格，並且恰好有一個貼圖使這兩個方塊都被圖塊佔據，則這兩個貼圖不同。
給定 N，那麼我們必須找到用 2xN 棋盤拼圖的方法有多少種？因此，如果輸入為 3，則輸出將為 5。因此，排列可以是 [XYZ XXZ XYY XXY XYY] 和 [XYZ YYZ XZZ XYY XXY]，這裡使用不同的字母表示不同的圖塊。
要解決此問題，我們將遵循以下步驟：
建立一個名為 dp 的大小為 N + 5 的陣列，設定 dp[1] := 1，dp[2] := 2 和 dp[3] := 5
對於範圍 4 到 N 中的 i
dp[i] := 2*dp[i – 1] + dp[i – 3]
返回 dp[N]
示例 (C++)
讓我們看看以下示例以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b){
return ((a % MOD) + (b % MOD)) % MOD;
}
class Solution {
public:
int numTilings(int N) {
vector <int> dp(N + 5);
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for(int i = 4; i <= N; i++){
dp[i] = add(2 * dp[i - 1], dp[i - 3]);
}
return dp[N];
}
};
main(){
Solution ob;
cout << (ob.numTilings(3));
}輸入
3
輸出
5
更新於：02-五月-2020
367 次瀏覽
廣告