[DjDiablo]

С другой стороны Я не уверен что разные объяснения как либо отражаются на структуре. Ну к примеру две последовательности 567 и 567567 можно объяснить как добавлением 567 слева так и добавлением 567 справа, это равнозначные варианты и выбрать можно любой.

окей если так посмотреть

33 2 567
33 4 567 3 567
здесь нам все равно было ли во втором случае 567 добавлено в конец или в середину

а вот здесь не все равно.
33 2 567 89 2 90
33 4 89 3 90 567

Вродебы 567 встречается и во втором случае.
Но у нас так же встречаются и 89 x 90.
если было добавлено 567 в конец то это три изменения
а если 89 90 в середину это аж четыре.
Вероятно 567 это добавленый элемент а не сохранившийся, так как добавление 567 потребует меньше трансформаций чем его сохранение. Ведь за сохранение трех чисел 567 мы вынуждены заплатить добавление аж 4х (89 x 90).

а вот ситуация по интереснее. В отличии от предыдущего примеру выбирать нужно между множеством обьяснений
1)
33 567 890 2 90 60
33 90 3 890 567 2 890 60
совпали 567 890 (6 совпадений)

2)
33 567 890 2 90 60
33 90 3 890 567 2 890 60
совпали 90 2 90 (5 совпадений)

3)
33 567 890 2 90 60
33 90 3 890 567 2 890 60
совпали 890 2 90 (6 совпадений)

4)
33 567 890 2 90 60
33 90 3 890 567 2 890 60
совпали 90 90 (4 совпадения)

5) ..... еще какие то

Гипотезы 1 и 3 требуют наименьшего числа изменений или можно сказать имеют наибольшее число совпадений между двумя массивами. Блядь, здесь как раз алгоритм Вагнера Фишера или алгоритм Хиршберга справляется

http://habrahabr.ru/post/117063/

P.S. 33 60 игнорирую чтобы не отвлекали, а так конечно они тоже участвуют
567 это не пятьсот шисят семь, а 5,6,7. Все числа от 0 до 9