डोमिनोज़ और ट्रोमिनो टाइलिंग सी++ . में

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

एक टाइलिंग में, प्रत्येक वर्ग को एक टाइल से ढंकना चाहिए। यहां दो टाइलिंग अलग-अलग हैं यदि और केवल तभी जब बोर्ड पर दो 4-प्रत्यक्ष रूप से आसन्न कोशिकाएं हों, जैसे कि टाइलिंग में से एक में दोनों वर्ग एक टाइल द्वारा कब्जा कर लिया गया हो।

N दिया गया है, तो हमें यह पता लगाना होगा कि हम 2xN बोर्ड को कितने तरीकों से टाइल कर सकते हैं? तो अगर इनपुट 3 है, तो आउटपुट 5 होगा। तो व्यवस्थाएं [XYZ XXZ XYY XXY XYY] और [XYZ YYZ XZZ XYY XXY] हो सकती हैं, यहां अलग-अलग टाइलों के लिए अलग-अलग अक्षरों का उपयोग किया जाता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

आकार N + 5 का dp नामक एक सरणी बनाएं, dp[1] सेट करें:=1, dp[2]:=2 और dp[3]:=5
मैं के लिए 4 से एन की सीमा में
- डीपी [i] :=2*dp[i - 1] + dp[i - 3]
वापसी डीपी [एन]

उदाहरण(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));
}