我有一个只包含非负整数的数组。现在我想将每个元素减少到零。唯一允许的操作是“将 i，j 范围内的每个元素减 1”，每个此类操作的成本为 1。现在的问题是如何找到可以将此数组转换为全零元素数组的此类操作的最小数量。
example: [1 2 3 0]
--->[0 1 2 0] (decrement all element in the range 0 to 2)
--->[0 0 1 0] (----------------------------range 1 to 2)
--->[0 0 0 0] (----------------------------range 2 to 2)
最佳答案
这感觉像是重复的，但我找不到任何证据，所以我会改为回答。
在每个最优解中，都不存在操作对 [a, b) 和 [b, c)，因为我们可以将它们合并为 [a, c)。此外，存在一个最优解是层流的，即对于每对操作，它们的范围是嵌套的或不相交的，但不是部分重叠的。这是因为我们可以将 [a, c) 和 [b, d) 上的操作转换为 [a, d) 和 [b, c)。
受制于后者的限制，只有一个最优策略直到置换操作，通过重复减少最大非零区间得出。 (归纳证明:考虑减少操作，其区间参数是最左边的并且是其他区间参数中的最大值。根据最左边的假设，这个区间必须包括最左边的非零元素。如果它排除了它右边的一个连续的非零元素，那么该元素怎么可能减少？不是从左边开始的间隔(那不会是层流的)，也不是从那个元素开始的间隔(那不是最优的)，所以根本不是。)
我们在算法上要做的就是构造这个最优解。在 Python 中:
cost = 0
stackheight = 0
for x in lst:
cost += max(x - stackheight, 0)
stackheight = x
关于algorithm - 将数组的每个元素减少为零，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23532342/