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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个称为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

以上是 该程序查找在Python中将列表转换为非递增列表所需的操作数 的全部内容， 来源链接： utcz.com/z/321461.html

回到顶部