ধরুন আমাদের দুটি ধরণের আকার রয়েছে, ডমিনো এবং ট্রোমিনো৷ তাদের নিচের মত ঘোরানো যেতে পারে −
একটি টাইলিং মধ্যে, প্রতিটি বর্গক্ষেত্র একটি টালি দ্বারা আবৃত করা আবশ্যক। এখানে দুটি টাইলিং আলাদা হয় যদি এবং শুধুমাত্র যদি বোর্ডে দুটি 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 থেকে 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
