C++-এ ডমিনো ও ট্রোমিনো দিয়ে 2xN এরিয়া পূরণের কনফিগারেশন সংখ্যা

মান লইয়া আমাদের দুটি শেপ আছে, ডমিনো (Domino) এবং ট্রোমিনো (Tromino)। ডমিনো 2 x 1 শেপ এবং ট্রোমিনো 'L' রকম শেপ। এগুলো রোটেট করা যায় নিচের মতো:

যদি আমাদের একটি নম্বর n থাকে, তবে 2 x n বোর্ডকে এই দুটি টাইপের পিস দিয়ে কতভাবে পূরণ করা যায় সেটা বের করতে হবে। টাইলিং-এ প্রতিটি স্কোয়ার একটি টাইল দিয়ে কভার করা থাকতে হবে।

তবে যদি ইনপুট 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] রিটার্ন করুন

বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

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