qwsqwa

手机串流 PS5 （ doge ）

招

@vegito2002 感觉可行，可以优化到 O(n*min(m,n))。

@contmonad 修改次数就是最长递减子序列。

DP：
原链表为 a ；
dp[n][m]，表示前 n 个数最小值大于等于 m 时需要的最小△值。
'''
def f(a):
ma = max(a)
dp = [[0] * (ma + 1) + [float("inf")] for _ in range(len(a) + 1)]

for i in range(1, len(a) + 1):
for j in range(ma, -1, -1):
dp[i][j] = min(dp[i][j + 1], dp[i - 1][j] + abs(a[i - 1] - j))

return dp[len(a)][0]
'''
时间复杂度 O(n*m)

这道题基本算法就是双指针，复杂度 O(n)，但没有用到有序这个条件。所以感觉可能会有时间复杂度更低的算法。
但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和，则必须遍历整个数组。

@paloalto 好吧，我的错。。。

@paloalto 可是文章里用的是百分比

@DT27 这个有问题，这里“-”只能出现一次。