В этом видео мы рассмотрим пять шагов, которые можно использовать в качестве основы для решения задач динамического программирования. Вы увидите, как эти шаги применяются к двум конкретным задачам динамического программирования: задаче поиска самой длинной возрастающей подпоследовательности и задаче оптимального размещения блоков. Пять шагов перечислены ниже: 1. Визуализация примеров 2. Поиск подходящей подзадачи 3. Поиск связей между подзадачами 4. Обобщение связей 5. Реализация решения подзадач по порядку После подробного рассмотрения этих задач, в конце видео мы также обсудим распространённые подзадачи, с которыми вы можете столкнуться при решении задач динамического программирования. Исправление ошибок: для задачи с блоками использование словаря решений работает только в том случае, если нам даны уникальные блоки — использование списка подзадач было бы лучшим способом решения, если бы мы хотели обрабатывать повторяющиеся блоки (аналогично тому, как мы решали задачу поиска самой длинной возрастающей подпоследовательности). Поддержка: / reducible Это видео было бы невозможно без библиотеки manim с открытым исходным кодом, созданной 3blue1brown:
Вот ссылка на репозиторий с кодом, использованным для создания анимации в этом видео:
Музыка: Прелюдия № 2 Криса Забриски распространяется по лицензии Creative Commons Attribution (
https://creativecommons.org/licenses/...) Источник:
Исполнитель:
Вся остальная музыка — Аакаш Ганди
