পাইথনে মাল্টিপ্লিকেশন অপারেশন দিয়ে সর্বোচ্চ স্কোর বের করার প্রোগ্রাম

মনে করুন nums এবং multipliers নামক দুটি অ্যারে আছে যাদের সাইজ যথাক্রমে n এবং m (n >= m)। অ্যারেগুলো ১-ইন্ডেক্সড। আমাদের প্রাথমিক স্কোর ০। আমরা ঠিক m অপারেশন করব। i-তম অপারেশনে (১-ইন্ডেক্সড):

nums-এর শুরু বা শেষ থেকে একটি মান x সিলেক্ট করুন।
multipliers[i] * x স্কোরে যোগ করুন।
x কে nums থেকে রিমুভ করুন।

m অপারেশনের পর সর্বোচ্চ স্কোর বের করতে হবে।

যেমন, ইনপুট nums = [5,10,15], multipliers = [5,3,2] হলে, আউটপুট হবে ১১৫ কারণ: ১৫ নিয়ে ৫ দিয়ে গুণ করলে ৭৫, তারপর ১০ নিয়ে ৩ দিয়ে গুণ করলে ৩০, মোট ১০৫, শেষে ৫ নিয়ে ২ দিয়ে গুণ করলে ১০, মোট ১১৫।

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

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

n := nums-এর সাইজ, m := multipliers-এর সাইজ
dp := ০ দিয়ে m x (m+1) সাইজের একটি ২ডি অ্যারে
i = m-1 থেকে ০ পর্যন্ত (উল্টো ক্রমে)
- j = i থেকে m-1 পর্যন্ত
  - 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])
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]