資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式：計算用多米諾骨牌和三連塊填充區域的配置數量
假設我們有兩種形狀，多米諾骨牌和三連塊。多米諾骨牌是 2 x 1 的形狀，三連塊是“L”形。它們可以像下面這樣旋轉：
如果我們有一個數字 n，我們需要找到用這兩種型別的碎片填充 2 x n 棋盤的配置數量。眾所周知，在鋪磚中，每個方格都必須被一個瓷磚覆蓋。
因此，如果輸入是 3，則輸出將是 5。因此，排列可以是 [XYZ XXZ XYY XXY XYY] 和 [XYZ YYZ XZZ XYY XXY]，這裡不同的字母用於不同的瓷磚。
為了解決這個問題，我們將遵循以下步驟：
建立一個名為 dp 的大小為 N + 5 的陣列，設定 dp[1] := 1，dp[2] := 2 和 dp[3] := 5
對於 i 從 4 到 N 的範圍
dp[i] := 2*dp[i − 1] + dp[i − 3]
返回 dp[N]
讓我們看看下面的實現，以便更好地理解：
示例
#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 solve(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.solve(3));
}輸入
3
輸出
5
更新於: 2020-12-25
74 次瀏覽
廣告