ধরি আমাদের একটি নাম্বার লিস্ট nums আছে যা একটি কোম্পানির স্টক প্রাইস ক্রোনোলজিকাল অর্ডারে রিপ্রেজেন্ট করে এবং আরেকটি মান k আছে। আমাদের সর্বোচ্চ k বার বায় এবং সেল করে সর্বোচ্চ প্রফিট বের করতে হবে (পहले বায় করতে হবে, তারপর সেল, আবার বায় করার আগে সেল করতে হবে)।
তাই, ইনপুট যদি prices = [7, 3, 5, 2, 3], k = 2 হয়, তবে আউটপুট হবে ৩, কারণ ৩-এ বায় করে ৫-এ সেল, আবার ২-এ বায় করে ৩-এ সেল করলে প্রফিট ৩ হয়।
সমাধানের ধাপগুলো:
dp()ফাংশন ডিফাইন করুন। এটিi, k, boughtনিবে- যদি
i == len(prices)বাk == 0, তবে- ০ রিটার্ন করুন
- যদি
boughtট্রু হয়, তবেmax(dp(i+1, k-1, False) + prices[i], dp(i+1, k, bought))রিটার্ন করুন
- অন্যথায়,
max(dp(i+1, k, True) - prices[i], dp(i+1, k, bought))রিটার্ন করুন
- মেইন মেথড থেকে
dp(0, k, False)কল করে রেজাল্ট রিটার্ন করুন
বেশি বুঝতে নিচের বাস্তবায়নটি দেখুন:
উদাহরণ
class Solution:
def solve(self, prices, k):
def dp(i, k, bought):
if i == len(prices) or k == 0:
return 0
if bought:
return max(dp(i + 1, k - 1, False) + prices[i], dp(i + 1, k, bought))
else:
return max(dp(i + 1, k, True) - prices[i], dp(i + 1, k, bought))
return dp(0, k, False)
ob = Solution()
prices = [7, 3, 5, 2, 3]
k = 2
print(ob.solve(prices, k))ইনপুট
[7, 3, 5, 2, 3], 2
আউটপুট
3
