Как доказать правильность этого алгоритма?

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-го значения не более bn.

Для завершения проверки результата есть еще один шаг. Чтобы доказать, что любое решение, в котором значение n превышает bn, может быть улучшено без увеличения этого максимального значения. Но это тривиально - просто опустите один из + 1s от первого значения, чтобы превысить bn, и у вас есть строго лучшее решение без большего максимума. Поэтому никакое решение, заканчивающееся с максимумом, превышающим bn, может быть лучше лучшего с максимальным не более bn.

Поэтому у нас есть оптимальное решение.