АиСД S01E11. Динамическое программирование. Часть 2
HTML-код
- Опубликовано: 15 сен 2024
- Алгоритмы и структуры данных. Семестр 1. Лекция 11.
На одиннадцатой лекции мы продолжили говорить про метод динамического программирования. Разобрали задачи нахождения редакционного расстояния и оптимального расположения текста.
Университет ИТМО, 2021 г.
Где актив? Это лучший препод на ютубе.
*Спасибо большое за видос! Круто: "...берём жизненные задачи.."*
Возможно неплохой идеей будет поиск цепочки преобразований для редакционного расстояния. Там неочевидно восстановление ответа по матрице.
(но подозреваю, что это просто дается как ДЗ)
Новая концовка топ)
@Pavel Mavrin а в 58:33 тоже про CHT?
на последнем слайде в цикле для t используем индекс j+1, а в его теле j-1 - противоречие, как с ним быть?
в русской школе это называется "метод Кнута", я так и не нашел, откуда это пошло изначально
Про j+1 и j-1 не вижу противоречия, там d[t, j-1] все-таки, а не d[i, j-1], а t < i всегда, так что то значение раньше нашего посчитается
На 14:40 непонятно, что значит "добавить b". Разве его не в верхнюю строку надо добавить? Просто выглядит так, словно вы отрезаете b из второй строки, хотя говорите при этом, что добавляете.
Да, мы добавляем b к первой строчке, по продолжению, кстати, понятно, что именно это и происходит
Почему на 11:11 именно сравнивается A[i-1] и B[i-1]? Почему не "Если A[i]==B[i]" И почему тогда наше d[i][j]==d[i-1][j-1]? Вот эти два момента вообще непонятны, и, соответственно, непонятно всё, что идет дальше.
потому что i, j это указатели на элемент за последним, поэтому чтобы сравнить последние надо 1 вычесть. а дальше если символы равны, то мы просто переходим к прошлым в обоих строках, ведь у нас все хорошо
@Pavel Mavrin о чем вы хотели рассказать на 38:50 ? не могу разобрать
Convex Hull Trick (CHT) :)