পাইথনে কার্ড গেম থেকে সর্বোচ্চ পয়েন্ট সংগ্রহ করার প্রোগ্রাম

একটি কার্ড গেমে লিনিয়ারলি সাজানো কার্ড থেকে সর্বোচ্চ পয়েন্ট বের করা হয়। কার্ড পিক করার সময় পয়েন্ট = cards[i-1] * cards[i] * cards[i+1]। শুরু এবং শেষে ১ মানের কার্ড থাকে।

ইনপুট উদাহরণ

cards = [7, 5, 9, 10]

আউটপুট: 1025

পদ্ধতি

রিকার্সিভ ফাংশন search(x, y) ব্যবহার করে সব সম্ভাব্য পিকের কম্বিনেশন চেক করা হয় এবং ম্যাক্সিমাম পয়েন্ট রিটার্ন করা হয়। এটি মূলত Matrix Chain Multiplication বা Burst Balloons সমস্যার ভেরিয়েন্ট।

পাইথন কোড

def solve(cards):
    def search(x, y):
        temp = 0
        for z in range(x + 1, y):
            temp = max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])
        return temp

    cards = [1] + cards + [1]  # শুরু ও শেষে ১ যোগ
    return search(0, len(cards) - 1)

# টেস্ট
print(solve([7, 5, 9, 10]))  # 1025

ব্যাখ্যা

• ইনডেক্স ১: 7×5×9 = 315
• নতুন ইনডেক্স ১: 7×9×10 = 630
• ইনডেক্স ১: 7×10 = 70
• শেষ কার্ড: 10
• মোট = 315 + 630 + 70 + 10 = 1025

নোট: এই রিকার্সিভ সমাধান এক্সপোনেনশিয়াল টাইম নেয়। DP মেমোইজেশন ব্যবহার করে অপ্টিমাইজ করা যাবে।