परिचय
मान लीजिए हमारे पास दो आकार हैं: डोमिनो (Domino) और ट्रोमिनो (Tromino)। डोमिनो 2×1 आकार के होते हैं और ट्रोमिनो 'L' जैसे आकार के होते हैं। उन्हें नीचे दिखाए अनुसार घुमाया जा सकता है।

यदि हमारे पास एक संख्या n है, तो हमें इन दो प्रकार के टुकड़ों से 2×n बोर्ड भरने के कॉन्फिगरेशन की संख्या ढूंढनी है। टाइलिंग में, हर वर्ग एक टाइल से ढका होना चाहिए।
तो यदि इनपुट 3 है, तो आउटपुट 5 होगा।
समाधान दृष्टिकोण
यह एक डायनामिक प्रोग्रामिंग समस्या है जिसमें पुनरावृत्ति संबंध है:
dp[i] = 2×dp[i-1] + dp[i-3]
आधार मामले: dp[1]=1, dp[2]=2, dp[3]=5
उदाहरण कोड
#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];
}
};
int main(){
Solution ob;
cout << (ob.solve(3));
return 0;
}
इनपुट
3
आउटपुट
5
निष्कर्ष
यह LeetCode "Domino and Tromino Tiling" समस्या (790) का समाधान है। पुनरावृत्ति dp[n] = 2*dp[n-1] + dp[n-3] अंतिम कॉलम में टाइल प्लेसमेंट पैटर्न से आती है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।