C++ में डोमिनोज़ और ट्रोमिनोज़ के साथ क्षेत्र को भरने के लिए कॉन्फ़िगरेशन की संख्या गिनने का कार्यक्रम है

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

यदि हमारे पास संख्या n है, तो हमें 2 x n बोर्ड को इन दो प्रकार के टुकड़ों से भरने के लिए कई विन्यासों को खोजना होगा। जैसा कि हम टाइलिंग में जानते हैं, प्रत्येक वर्ग को एक टाइल से ढंकना चाहिए।

तो अगर इनपुट 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 से एन की सीमा में
- dp[i] :=2*dp[i - 1] + dp[i - 3]
वापसी डीपी [एन]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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));
}