如何證明此算法的正確性？

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)是使用解決方案進行清算的最小成本，其中n th值最多爲bn。

爲了完成證明結果還有一步。這是爲了證明任何解決方案，其中的值超過bn th的值可以在不增加該最大值的情況下得到改進。但這很簡單 - 只需從第一個值中忽略+1中的一個，即可超過bn，並且您有一個嚴格的更好的解決方案，而不會有較大的最大值。因此，最大不超過bn的解決方案最多可以優於最大最大數bn。

因此我們有最佳的解決方案。