Giả sử chúng ta có một danh sách các số được gọi là nums. Bây giờ chúng ta hãy xem xét một phép toán trong đó chúng ta lấy hai giá trị liên tiếp và hợp nhất nó thành một giá trị bằng cách lấy tổng của chúng. Chúng ta phải tìm số lượng thao tác tối thiểu cần thiết để danh sách biến thành không tăng.
Vì vậy, nếu đầu vào giống như nums =[2, 6, 4, 10, 2], thì đầu ra sẽ là 2, vì chúng ta có thể hợp nhất [2, 6] để có được [8, 4, 10, 2] và sau đó hợp nhất [8, 4] để có [12, 10, 2].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu nums trống, thì
-
trả về 0
-
-
chèn −inf vào cuối nums
-
N:=kích thước của nums
-
dp:=danh sách kích thước N và điền bằng 0
-
arr:=danh sách kích thước N và điền bằng 0
-
p:=kích thước của arr
-
arr [p − 1]:=nums [N − 1]
-
arr [p − 2]:=nums [N − 2]
-
đối với tôi trong phạm vi N - 3 đến 0, giảm đi 1, thực hiện
-
j:=i
-
x:=nums [j]
-
while j
-
j:=j + 1
-
x:=x + nums [j]
-
-
dp [i]:=j - i + dp [j + 1]
-
arr [i]:=x
-
-
trả về dp [0]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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)) Đầu vào
[2, 6, 4, 10, 2]
Đầu ra
2