数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：计算将列表转换为非递增列表所需的运算次数
假设我们有一个名为nums的数字列表。现在让我们考虑一个操作，我们将两个连续的值合并成一个值，方法是将它们相加。我们必须找到使列表变为非递减所需的最小操作次数。
因此，如果输入类似于nums = [2, 6, 4, 10, 2]，则输出将为2，因为我们可以将[2, 6]合并得到[8, 4, 10, 2]，然后将[8, 4]合并得到[12, 10, 2]。
为了解决这个问题，我们将遵循以下步骤：
如果nums为空，则
返回0
在nums的末尾插入-∞
N := nums的大小
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 := i
x := nums[j]
当j < N - 1且x < arr[j + 1]时，执行：
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))输入
[2, 6, 4, 10, 2]
输出
2
更新于：2020-12-25
浏览量：100
广告