Динамическое программирование. Теория и практика
В этом видео мы переходим от графов и топологической сортировки к динамическому программированию и показываем, как зависимости между состояниями задают порядок вычислений в динамике. На простых примерах объясняем, из чего же состоит динамика (состояния, инициализация, переходы). Разбираем задачи на подсчёт числа путей, поиск пути с максимальной суммой, а также разные техники реализации динамики. Во второй части видео идёт серия разборов типовых задач, которые помогают закрепить общий шаблон динамического программирования на практике. Задачи: https://codeforces.com/group/uQw4LhzOcG/contest/684209 Тайм-коды: 00:00:00 Вспоминаем различные способы обхода графа 00:02:30 Ориентированные ациклические графы 00:06:20 Что такое топологическая сортировка 00:10:30 Динамическое программирование 00:13:00 Задача о зайчике и количестве путей от 1 до n 00:17:00 Пример задачи из ЕГЭ по информатике 00:19:00 Способ вычисления числа путей 00:21:20 Выводим формулу перехода в динамике 00:25:25 Пример динамики с числами Фибоначчи 00:30:30 Поиск пути с максимальной суммой 00:35:15 Формула пересчёта динамики в общем случае 00:38:00 Вариация задачи, в которой запрещены заданные клетки 00:44:00 Два вида динамики: push и pull 00:46:10 Барьерные элементы и выход за пределы массива 00:47:50 Задача «А. Лестница» 00:52:29 Задача «B. Зайчик» 01:02:46 Задача «C. Путь домой» 01:04:34 Задача «E. Наибольшее возрастание» 01:05:35 Задача «F. Ядра» 01:24:25 Задача «M. Разрежь ленточку» 01:28:13 Задача «H. Длинные прыжки» 01:33:40 Задача «G. Новогоднее число»
В этом видео мы переходим от графов и топологической сортировки к динамическому программированию и показываем, как зависимости между состояниями задают порядок вычислений в динамике. На простых примерах объясняем, из чего же состоит динамика (состояния, инициализация, переходы). Разбираем задачи на подсчёт числа путей, поиск пути с максимальной суммой, а также разные техники реализации динамики. Во второй части видео идёт серия разборов типовых задач, которые помогают закрепить общий шаблон динамического программирования на практике. Задачи: https://codeforces.com/group/uQw4LhzOcG/contest/684209 Тайм-коды: 00:00:00 Вспоминаем различные способы обхода графа 00:02:30 Ориентированные ациклические графы 00:06:20 Что такое топологическая сортировка 00:10:30 Динамическое программирование 00:13:00 Задача о зайчике и количестве путей от 1 до n 00:17:00 Пример задачи из ЕГЭ по информатике 00:19:00 Способ вычисления числа путей 00:21:20 Выводим формулу перехода в динамике 00:25:25 Пример динамики с числами Фибоначчи 00:30:30 Поиск пути с максимальной суммой 00:35:15 Формула пересчёта динамики в общем случае 00:38:00 Вариация задачи, в которой запрещены заданные клетки 00:44:00 Два вида динамики: push и pull 00:46:10 Барьерные элементы и выход за пределы массива 00:47:50 Задача «А. Лестница» 00:52:29 Задача «B. Зайчик» 01:02:46 Задача «C. Путь домой» 01:04:34 Задача «E. Наибольшее возрастание» 01:05:35 Задача «F. Ядра» 01:24:25 Задача «M. Разрежь ленточку» 01:28:13 Задача «H. Длинные прыжки» 01:33:40 Задача «G. Новогоднее число»