在Python中找出将列表转换为非递增列表所需的操作数

假设我们有一个名为nums的数字列表。现在让我们考虑一个操作，其中我们取两个连续的值并将其合并为一个值，方法是取它们的和。我们必须找到所需的最小操作数，以使列表变为非递增。

因此，如果输入如下所示：nums = [2, 6, 4, 10, 2]，则输出将为2，因为我们可以合并[2,6]以获得[8, 4, 10, 2]，然后合并[8, 4]以获得[12, 10, 2]。

要解决这个问题，我们将按照以下步骤执行-

如果nums为空，则
- 返回0
在nums的末尾插入-inf
N := nums的大小
dp :=一个大小为N的列表，并用0填充
arr: = 一个大小为N的列表，并用0填充
p: = arr的大小
arr[p-1] := nums[N-1]
arr[p-2] := nums[N-2]
对于i在范围N – 3到0，每次递减1，执行以下操作
- j := i
- x := nums j
- 当j
- j := j +1
- x: = x + nums [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))