Где применяется
1. Задача
Ещё в уроке 105 ты выдавал сдачу жадно: брал самую большую монету, которая помещается в остаток, и повторял. Для обычных денег это всегда даёт наименьшее число монет. Но там же выяснилось, что правило работает только на «каноническом» наборе монет (наборе, где жадный выбор всегда оптимален).
Вот набор, на котором оно ломается. Монеты [1, 3, 4], нужно выдать 6. Жадный выбор берёт 4, потом две 1: 4 + 1 + 1, три монеты. А 3 + 3 это всего две монеты. Большая монета, взятая первой, оставила остаток 2, который собирается только двумя единицами.
Для таких наборов жадный приём не годится. Нужен метод, который пробует каждую монету на каждой сумме и запоминает лучшее. Это делает таблица. Она возвращает наименьшее число монет, которые дают сумму, или -1, если сумму нельзя собрать точно. Каждую монету можно брать сколько угодно раз.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- лучшее/максимум/минимум, заканчивающееся в позиции i
- число способов дойти, подняться или замостить
- нельзя брать два соседних элемента
- минимальная стоимость пути по сетке
- повторяющиеся подзадачи, одно и то же состояние считается заново
Похоже, но не то
- Рекурсия с мемоизацией (Recursion with memoization)
Мемоизация заполняет ту же таблицу сверху и по требованию. Здесь она заполняется снизу в заданном порядке.
- Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))
Жадность выбирает один вариант на шаг. Динамика держит все варианты до конца.
- Рекурсия (Recursion)
Рекурсия показывает, каким будет переход. Скорость даёт именно таблица.
- DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance))
Там состояние это пара позиций в двух последовательностях. Здесь хватает одного индекса.
n состояний по O(1) работы дают O(n). Память падает до O(1), когда важны только последние состояния.
На LeetCode
Задачи, где сумму собирают из частей, которые можно брать повторно, и спрашивают наименьшее число частей или число способов. Таблица по сумме, заполненная от 0 вверх, пробует каждую часть на каждой сумме.
Задача урока. Сумма 0 собирается из нуля монет, а сумма, которая к концу осталась бесконечностью, даёт минус 1.
Здесь таблица считает способы. Ставь цикл по монетам снаружи цикла по сумме, чтобы каждый набор монет считался один раз при любом порядке.
Монеты здесь это квадраты до n, и таблица даёт наименьшее их число с суммой n.
Здесь разный порядок считается разными ответами, поэтому цикл по сумме идёт снаружи, а по числам внутри.