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

ধরুন আমাদের যথাক্রমে n এবং m আকারের দুটি অ্যারে সংখ্যা এবং গুণক রয়েছে (n>=m)। অ্যারেগুলি 1-সূচীযুক্ত। এখন আমাদের প্রাথমিক স্কোর 0। আমরা ঠিক m অপারেশন করতে চাই। ith অপারেশনে (1-সূচিবদ্ধ), আমরা −

করব

সংখ্যার শুরু বা শেষ থেকে x থেকে একটি মান নির্বাচন করুন।
স্কোরে গুণক [i] * x যোগ করুন।
অ্যারে সংখ্যা থেকে x সরান।

m অপারেশন করার পর আমাদের সর্বোচ্চ স্কোর খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি nums =[5,10,15], গুণক =[5,3,2] এর মত হয়, তাহলে আউটপুট হবে 115 কারণ আমরা 15 নিতে পারি তারপর 5*15 =75 পেতে এটিকে 5 দিয়ে গুণ করি। , তারপর 10*3 =30, তাহলে মোট হল 75+30 =105 এবং অবশেষে 5*2 =10, তাই মোট 105+10 =115৷

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

n :=সংখ্যার আকার, m :=আকার গুণক
dp :=m x (m+1) আকারের একটি 2D অ্যারে এবং 0 দিয়ে পূরণ করুন
আমি তালিকার সীমা 0 থেকে m - 1 এর বিপরীতে, কর
- j এর জন্য i থেকে m - 1 রেঞ্জে, do
  - k :=i + m - j - 1
  - dp[i, j] =সর্বাধিক (nums[i] * multipliers[k] + dp[i+1, j]) এবং (সংখ্যা[j-m+n] * গুণক [k] + dp[i, j -1])
dp[0]
এর শেষ উপাদান ফেরত দিন

উদাহরণ

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

def solve(nums, multipliers):
   n, m = len(nums), len(multipliers)
   dp = [[0]*m for _ in range(m+1)]

   for i in reversed(range(m)):
      for j in range(i, m):
         k = i + m - j - 1
         dp[i][j] = max(nums[i] * multipliers[k] + dp[i+1][j], nums[j-m+n] * multipliers[k] + dp[i][j-1])

   return dp[0][-1]

nums = [5,10,15]
multipliers = [5,3,2]
print(solve(nums, multipliers))

ইনপুট

[5,10,15], [5,3,2]