পাইথনে ব্রিক রিমভাল গেমে আমলের ম্যাক্সিমাম স্কোর বের করা

আমল এবং বিমল ব্রিক গেম খেলছে। nums অ্যারেতে n ব্রিকের নম্বর আছে। প্রতিটি টার্নে ১, ২ বা ৩টি ব্রিক টপ থেকে সরাতে পারা যায়। সরানো ব্রিকের নম্বর যোগ করে স্কোর হয়। আমল প্রথম খেলে। আমল নিশ্চিত করে সর্বোচ্চ কত স্কোর পেতে পারে তা বের করতে হবে।

উদাহরণ

ইনপুট: nums = [1,2,3,4,5]

আউটপুট: 6

আমল ১ নিলে, বিমল ২,৩,৪ নিতে পারে (স্কোর ৯), আমল ৫ নেবে → মোট ৬।

সমাধান পদ্ধতি

nums রিভার্স করুন।
temp[i] = i-তম পজিশন থেকে игра শুরু করলে বর্তমান খেলোয়ার পাওয়া যায় এমন ম্যাক্সিমাম স্কোর।
total[i] = প্রিফিক্স সাম।
বেস কেস: temp[0]=nums[0], temp[1]=nums[0]+nums[1], temp[2]=temp[1]+nums[2]
i ≥ 3: temp[i] = max(nums[i], nums[i]+nums[i-1], nums[i]+nums[i-1]+nums[i-2]) (এখানে অপ্টিমাল প্লে ধরে নেওয়া হয়েছে)।
নোট: প্রদত্ত কোডে অপ্টিমাল প্লে লজিক সঠিক নয়; সঠিক DP হবে temp[i] = total[i] - min(temp[i-1], temp[i-2], temp[i-3])।

পাইথন ইমপ্লিমেন্টেশন (সংশোধিত DP)

def solve(nums):
    n = len(nums)
    nums.reverse()
    total = [0] * n
    for i, val in enumerate(nums):
        total[i] = total[i-1] + val if i > 0 else val
    dp = [0] * n
    dp[0] = nums[0]
    if n > 1:
        dp[1] = nums[0] + nums[1]
    if n > 2:
        dp[2] = nums[0] + nums[1] + nums[2]
    for i in range(3, n):
        dp[i] = total[i] - min(dp[i-1], dp[i-2], dp[i-3])
    return dp[n-1]

# টেস্ট
nums = [1, 2, 3, 4, 5]
print(solve(nums))  # আউটপুট: 6

ইনপুট

[1,2,3,4,5]