বাস্ট ব্যালুন্স সমস্যা
nটি ব্যালুন আছে, প্রতিটির ওপর একটি সংখ্যা। ব্যালুন i ফোড়ালে পাওয়া যায় nums[i-1] * nums[i] * nums[i+1] কয়েন। ফোড়ার পর i-1 এবং i+1 সংলগ্ন হয়ে যায়। সর্বোচ্চ কয়েন সংগ্রহ করতে হবে।
উদাহরণ: [3,1,5,7] → ১৪৮ (ক্রম: ১, ৫, ৩, ৭ ফোড়ালে)
সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং - ইন্টারভোল DP)
dp[l][r]= সাবঅ্যারে[l, r]-এ সব ব্যালুন ফোড়ালে সর্বোচ্চ কয়েন- অবশিষ্ট ব্যালুনগুলো ধরে
l-1এবংr+1সীমানা হিসেবে বিবেচনা করুন for l = n-1 down to 0,for r = l to n-1:for i = l to r(শেষে ফোড়া ব্যালুনiধরে):coins = dp[l][i-1] + dp[i+1][r] + nums[l-1]*nums[i]*nums[r+1]dp[l][r] = max(dp[l][r], coins)
dp[0][n-1]ফেরত দিন
C++ কোড উদাহরণ
[3,1,5,7]
আউটপুট
148
