পাইথনে ইট লেগো ব্রিক দিয়ে হরিজন্টাল প্যাটার্ন সংখ্যা বের করা

বিভিন্ন লেংথের ব্রিক দেওয়া আছে (প্রস্থ ১)। দেয়া প্রস্থ ও উঁচুয়ের জন্য পুরো লেআউট বানাতে কতভাব সম্ভব তা বের করুন। ব্রিক শুধু হরিজন্টালি রাখা যাবে।

ইনপুট উদাহরণ

bricks = [2, 1]
width = 3
height = 2

আউটপুট: 9

অ্যালগরিদম

1. DP অ্যারে w বানান যেখানে w[i] = প্রস্থ i বানाने উপায়ের সংখ্যা।
2. w[0] = 1 (খালি প্রস্থ ১ ভাবে বানানো যায়)।
3. প্রতিটি প্রস্থের জন্য সব ব্রিক ট্রাই করুন।
4. ফাইনাল আন্স = w[width] ** height (প্রতিটি সারি স্বতন্ত্র)।

পাইথন কোড

def solve(bricks, width, height):
    w = [1] + [0] * width
    for i in range(width):
        if w[i]:
            for x in bricks:
                if i + x <= width:
                    w[i + x] += w[i]
    return w[width] ** height

# টেস্ট
print(solve([2, 1], 3, 2))  # 9

ব্যাখ্যা

প্রথম DP দিয়ে এক সারি বানানোর উপায় বের করা হয়, তারপর height ঘাত করলে মোট প্যাটার্ন পাওয়া যায় কারণ সারিগুলো স্বতন্ত্র।