algorithm - 如何证明这个算法的正确性？

Question

我正在解决来自 codeforces 的问题.

我们的工作是找到使给定整数序列成为非递减序列的最小成本。我们可以在每个步骤中将序列的任意数量增加/减少 1，这将花费 1。

例如，当我们得到一个序列 3、2、-1、2、11 时，我们可以使该序列以成本 4 不递减(通过将 3 递减为 2 并将 -1 增加到 2，因此非递减序列将是 2, 2, 2, 2, 11)

根据editorial对于这个问题，我们可以使用具有 2 个序列的动态规划来解决这个问题，(一个是我们给定的序列，另一个是给定序列的排序序列)。

解决方案概要:

如果我们让 a 是原始序列，b 是序列 a 的排序序列，并且让 f( i,j) 是获得前i个元素非递减且第i个元素至多为bj的序列所需的最少步数。那么我们可以如下进行递归。 (这是来自问题的社论)

f(1,1)=|a1-b1|
f(1,j)=min{|a1-bj|,f(1,j-1)},  j>1
f(i,1)=|ai-b1|+f(i-1,1),  i>1
f(i,j)=min{f(i,j-1),f(i-1,j)+|ai-bj|},  i>1, j>1

我理解这种重复。但是，我不明白为什么我们应该将原始序列与排序后的序列进行比较，而且我不确定我们是否可以使用给定序列的排序序列以外的另一个序列获得正确的最小成本。

我们如何证明这个解决方案的正确性？我们如何保证排序序列的答案是最小成本？

Answer 1

练习的重点是可以通过归纳来证明这种重复发生。一旦它被证明，那么我们就证明了 f(n,n) 是结束一个解决方案的最低成本，其中 nth 值最多为 bn.

要完成对结果的证明，还有一个步骤。这是为了证明任何第 n 值超过 bn 的解决方案都可以在不增加最大值的情况下得到改进。但这是微不足道的 - 只需从第一个值中省略一个 +1 以超过 bn 并且你有一个严格更好的解决方案而没有更大的最大值。因此，没有一个解决方案的最大值大于 bn 可以比最大值最多为 bn 的最佳解决方案更好。

因此我们有最优解。