পাইথনে সংখ্যাগুলি মুছে দিয়ে সর্বাধিক সংযোজন স্কোর খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় সংখ্যা। আসুন আমরা এমন একটি অপারেশন বিবেচনা করি যেখানে আমরা একটি সংখ্যা নির্বাচন করতে পারি, তারপর এটিকে সরিয়ে ফেলি এবং সংখ্যার যোগফল এবং এর দুটি সন্নিহিত সংখ্যা দ্বারা আমাদের স্কোর বৃদ্ধি করি। যদি আমরা এই অপারেশনটি যতবার চাই ততবার করতে পারি যতক্ষণ না আমরা তালিকার প্রথম বা শেষ নম্বরটি নির্বাচন করি না। আমাদের সম্ভাব্য সর্বাধিক স্কোর খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি nums =[2, 3, 4, 5, 6] এর মত হয়, তাহলে আউটপুট হবে 39, যেমন আমরা 5 নির্বাচন করতে পারি, তাহলে যোগফল হবে (4 + 5 + 6) =15, অ্যারে হবে হবে [2, 3, 4, 6], তারপর 4 নির্বাচন করুন, তাই যোগফল হল (3 + 4 + 6) =13, এবং অ্যারে হবে [2, 3, 6], 3 নির্বাচন করুন, যোগফল হবে (2 + 3) + 6) =11, তাই মোট যোগফল হল 15 + 13 + 11 =39

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=সংখ্যার আকার
যদি n <3 হয়, তাহলে:
- আকারের একটি 2D অ্যারে সংজ্ঞায়িত করুন (n + 1) x (n + 1)
লেন শুরু করার জন্য :=3, যখন len <=n, আপডেট করুন (লেন 1 দ্বারা বাড়ান), −
- আরম্ভ করার জন্য i :=1, যখন i + len - 1 <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), −
  - r :=i + len - 1
  - উত্তর :=0
  - আরম্ভ করার জন্য k :=i + 1, যখন k <=r - 1, আপডেট করুন (k 1 দ্বারা বাড়ান), −
    - curr :=dp[i, k] + dp[k, r] + nums[k - 1]
    - যদি curr> ans, তারপর:
  - উত্তর :=উত্তর + সংখ্যা[i - 1] + সংখ্যা[r - 1]
  - dp[i, r] :=ans
রিটার্ন dp[1, n]

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& nums) {
      int n = nums.size();
      if (n < 3) return 0;
         vector<vector<int>> dp(n + 1, vector<int>(n + 1));
         for (int len = 3;
            len <= n; ++len) {
               for (int i = 1; i + len - 1 <= n; ++i) {
                  int r = i + len - 1;
                  int ans = 0;
               for (int k = i + 1; k <= r - 1; ++k) {
                  int curr = dp[i][k] + dp[k][r] + nums[k - 1];
                  if (curr > ans)
                     ans = curr;
               }
               ans += nums[i - 1] + nums[r - 1]; dp[i][r] = ans;
         }
      }
      return dp[1][n];
   }
};
int solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
main(){
   vector<int> v = {2, 3, 4, 5, 6};
   cout << solve(v);
}

ইনপুট

[2, 3, 4, 5, 6]