Я изучаю динамическое программирование c и столкнулся с проблемой на примере поиска оптимального выравнивания для 2 строк. Приведенный ниже абзац взят из учебника.
Существует три возможных варианта создания текущего состояния: , если символ перемещается вдоль более короткой строки для лучшего возможного выравнивания, стоимость равна 1 и записывается по количеству столбцов массива. Если новый символ вставлен, стоимость равна 1 и отражается в оценке строки массива. Если выравниваемые символы отличаются, сдвиг и вставка, стоимость равна 2; или если они идентичны, стоимость равна 0; это отражается в диагонали массива. На рисунке 4.5 показана инициализация, увеличение + 1 в первой строке и столбце отражает продолжающееся смещение или вставку символов в «_» или пустую строку.
Часть, которую я не понимаю, выделена жирным шрифтом. Что они значат на самом деле? Какой персонаж смещен и в каком направлении? Что означает вставка нового символа, я имею в виду, какой символ они вставляют?
Я полностью понимаю, как работает алгоритм, принимая во внимание верхнее, левое и диагональное значения и выбирая наилучшее значение из трех. Однако, почему они инициализируют массив таким образом, особенно в части смещения и вставки, возможно, процессы могут быть показаны графически.