ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় সংখ্যা। এখন আমরা একটি ক্রিয়াকলাপ বিবেচনা করি যেখানে আমরা পরপর দুটি মান গ্রহণ করি এবং তাদের যোগফল নিয়ে এটিকে একটি মানতে মার্জ করি। আমাদের প্রয়োজনীয় ন্যূনতম সংখ্যক ক্রিয়াকলাপ খুঁজে বের করতে হবে যাতে তালিকাটি অ-বৃদ্ধিতে পরিণত হয়।
সুতরাং, ইনপুট যদি nums =[2, 6, 4, 10, 2] এর মত হয়, তাহলে আউটপুট হবে 2, যেমন আমরা [2, 6] মার্জ করে [8, 4, 10, 2] পেতে পারি এবং তারপর [12, 10, 2] পেতে [8, 4] মার্জ করুন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
যদি সংখ্যা খালি হয়, তাহলে
-
রিটার্ন 0
-
-
সংখ্যার শেষে −inf ঢোকান
-
N :=সংখ্যার আকার
-
dp :=N আকারের একটি তালিকা এবং 0
দিয়ে পূরণ করুন -
arr :=N আকারের একটি তালিকা এবং 0
দিয়ে পূরণ করুন -
p :=arr এর আকার
-
arr[p−1] :=সংখ্যা[N−1]
-
arr[p−2] :=সংখ্যা[N−2]
-
N − 3 থেকে 0 রেঞ্জের i জন্য, 1 দ্বারা হ্রাস করুন, করুন
-
j :=i
-
x :=সংখ্যা[j]
-
যখন j
-
j :=j + 1
-
x :=x + সংখ্যা[j]
-
-
dp[i] :=j − i + dp[j + 1]
-
arr[i] :=x
-
-
dp[0]
ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution:
def solve(self, nums):
if not nums:
return 0
nums.append(float("−inf"))
N = len(nums)
dp = [0] * N
arr = [0] * N
arr[−1] = nums[−1]
arr[−2] = nums[−2]
for i in range(N − 3, −1, −1):
j = i
x = nums[j]
while j < N − 1 and x < arr[j + 1]:
j += 1
x += nums[j]
dp[i] = j − i + dp[j + 1]
arr[i] = x
return dp[0]
ob = Solution()
nums = [2, 6, 4, 10, 2]
print(ob.solve(nums)) ইনপুট
[2, 6, 4, 10, 2]
আউটপুট
2
