АиСД S01E11. Динамическое программирование. Часть 2

[@legopro156]

Где актив? Это лучший препод на ютубе.

[@PASHKET_guitar]

*Спасибо большое за видос! Круто: "...берём жизненные задачи.."*

[@Sancho_Merka]

Возможно неплохой идеей будет поиск цепочки преобразований для редакционного расстояния. Там неочевидно восстановление ответа по матрице. (но подозреваю, что это просто дается как ДЗ)

[@ok_pavel]

Почему на 11:11 именно сравнивается A[i-1] и B[i-1]? Почему не "Если A[i]==B[i]" И почему тогда наше d[i][j]==d[i-1][j-1]? Вот эти два момента вообще непонятны, и, соответственно, непонятно всё, что идет дальше.

[@АлександрАлександр-н9ж6ш]

потому что i, j это указатели на элемент за последним, поэтому чтобы сравнить последние надо 1 вычесть. а дальше если символы равны, то мы просто переходим к прошлым в обоих строках, ведь у нас все хорошо

[@ok_pavel]

На 14:40 непонятно, что значит "добавить b". Разве его не в верхнюю строку надо добавить? Просто выглядит так, словно вы отрезаете b из второй строки, хотя говорите при этом, что добавляете.

[@НикитаВасильев-в7и]

Да, мы добавляем b к первой строчке, по продолжению, кстати, понятно, что именно это и происходит

[@innokentiyromanchenko1450]

@Pavel Mavrin а в 58:33 тоже про CHT? на последнем слайде в цикле для t используем индекс j+1, а в его теле j-1 - противоречие, как с ним быть?

[@pavelmavrin]

в русской школе это называется "метод Кнута", я так и не нашел, откуда это пошло изначально

[@pavelmavrin]

Про j+1 и j-1 не вижу противоречия, там d[t, j-1] все-таки, а не d[i, j-1], а t < i всегда, так что то значение раньше нашего посчитается

[@innokentiyromanchenko1450]

@Pavel Mavrin о чем вы хотели рассказать на 38:50 ? не могу разобрать

[@pavelmavrin]

Convex Hull Trick (CHT) :)

[@stepan8539]

Новая концовка топ)