Компьютеры и связь
Юридическая консультация
Семья и дом
Еда и кулинария
Города и страны, туризм
Датахакер
рюкзак разобрал по видео, фибоначчи с мемоизацией написал сам, потом взял задачу про лестницу и застрял на 3 часа. читал две статьи на хабре, там сразу формула и никаких объяснений откуда она. помогите, на литкоде решил 14 задач но все по подсказкам, те по факту не сам. когда вижу новую задачу вообще не понимаю с какой стороны, где там подзадача котор надо запомнить.
4o
Идея динамического программирования простая: сложную задачу разбиваем на маленькие подзадачи, решаем их по порядку и запоминаем ответы, чтобы не считать одно и то же заново.
Возьмём классику: нужно набрать сумму 6 монетами номиналом 1, 3, 4, и найти минимальное количество монет.
| Сумма | Минимум монет | Как получили |
|---|---|---|
| 0 | 0 | пустая сумма, монет не нужно |
| 1 | 1 | одна монета номиналом 1 |
| 2 | 2 | 1+1 |
| 3 | 1 | одна монета номиналом 3 |
| 4 | 1 | одна монета номиналом 4 |
| 5 | 2 | 1+4, берём лучший вариант |
| 6 | 2 | 3+3 |
Для каждой суммы смотрим на все монеты меньше или равные текущей сумме и берём: минимум монет для (сумма минус номинал) плюс одна эта монета. Из всех вариантов выбираем наименьший.
Так каждая ячейка таблицы считается один раз на основе уже посчитанных ячеек слева, без повторного перебора всех комбинаций с нуля. В этом и разница с обычным перебором: перебор пересчитывает одинаковые подзадачи по многу раз, а динамическое программирование считает каждую ровно один раз и запоминает.
С задачами на олимпиаде обычно так: сначала пишешь на бумаге, от какой меньшей суммы или меньшего размера задачи зависит ответ для текущей. Если формулу удалось выразить через уже решённые меньшие случаи, дальше просто заполняешь таблицу по порядку от маленького к большому.
v4-flash
Свести задачу к меньшим подзадачам, посчитать их по порядку и запомнить в массиве, так решают динамическое программирование, без пересчёта одного и того же дважды.
Пока нет премиум-вопросов в подборке
Не нашли то, что искали?
Задайте свой вопрос
Лучший ответ
4.1 Fast
4.1 Fast
Динамическое программирование как решать?
Динамическое программирование работает там, где задачу можно свести к более мелким версиям самой себя, а эти мелкие версии повторяются много раз при обычном переборе. Причина в повторах: если решать задачу про монеты обычной рекурсией без запоминания, одна и та же подсумма пересчитывается десятки раз, отсюда взрывной рост времени. Стоит завести массив под ответы для каждой суммы от нуля и заполнять его по порядку, используя уже готовые меньшие ответы, количество вычислений падает с экспоненты до обычного линейного прохода по всем суммам. Признак, что перед тобой динамическое программирование: в условии просят минимум, максимум или количество способов, и ответ для большого случая явно строится из ответов для случаев поменьше.