मान लीजिए हमारे पास दो प्रकार के आकार हैं, डोमिनो और ट्रोमिनो। उन्हें नीचे दिखाए अनुसार घुमाया जा सकता है:

एक टाइलिंग में, प्रत्येक वर्ग को एक टाइल द्वारा कवर किया जाना चाहिए। यहां दो टाइलिंग तभी अलग हैं जब बोर्ड पर दो 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सेट करेंiको 4 सेNतक लूप करें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