该程序查找在Python中将列表转换为非递增列表所需的操作数

假设我们有一个称为nums的数字列表。现在让我们考虑一个运算，我们取两个连续的值，然后取它们的和将它们合并为一个值。我们必须找到所需的最小操作数，以便列表变为非递增。

因此，如果输入类似于nums = [2，6，4，10，2]，则输出将为2，因为我们可以合并[2，6]以得到[8，4，10，2]，然后合并[8，4]以获得[12，10，2]。

为了解决这个问题，我们将遵循以下步骤-

• 如果nums为空，则

• 返回0

• 在num的末尾插入-inf

• N：=数字的大小

• dp：=大小为N并填充0的列表

• arr：=大小为N并填充0的列表

• p：= arr的大小

• arr [p-1]：= nums [N-1]

• arr [p-2]：= nums [N-2]

• 对于范围在N − 3至0的i，减1，

• j：= j + 1

• x：= x +数字[j]

• j：=我

• x：= nums [j]

• 当j <N − 1且x <arr [j + 1]时，

• 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