C++-এ ডমিনো ও ট্রোমিনো টাইলিং

দুটি রকমের আকার দেওয়া আছে: ডমিনো আর ট্রোমিনো। এগুলো নিচের মতো ঘুরানো যায়:

একটি টাইলিং-এ প্রতিটি চতুর্ভুজ টাইল দিয়ে ঢাকা থাকতে হবে। দুটি টাইলিং আলাদা হবে যদি ও тільки যদি বোর্ডে দুটি ৪-দিকনির্দেশিত সन्नিহিত কোষ্ঠ থাকে যেন একটি টাইলিং-এ দুটি কোষ্ঠই টাইল দিয়ে ঢাকা থাকে অন্যটিতে নয়।

N দেওয়া থাকলে, ২xN বোর্ড কতভাবে টাইল করা যায়? ইনপুট ৩ হলে আউটপুট ৫। বিন্যাসগুলো হতে পারে [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)); }