该程序查找在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