Где применяется
1. Задача
Робот стоит в левом верхнем углу сетки склада и должен добраться до правого нижнего угла. Он ходит только вправо или вниз, по одной клетке за ход. При планировании возникают два вопроса. Сколько всего разных маршрутов? И какой маршрут самый дешёвый, если проход через каждую клетку чего-то стоит (там тесно или там подъём)?
Перебирать маршруты вручную быстро становится невозможно. У сетки 8 на 8 их уже 3432, а на реальном плане склада клеток намного больше.
В прошлом уроке ты заполнял один ряд ячеек. Здесь ответ зависит от двух координат, строки и столбца, поэтому ряд превращается в сетку ячеек. Идея та же: каждую ячейку заполняешь из ячеек, которые уже заполнил.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 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
Задачи на сетку, где двигаться можно только вправо или вниз, а нужно число маршрутов или самый дешёвый маршрут. Каждая клетка получается из верхней и левой, так что один проход по строкам заполняет таблицу.
Это countPaths из урока без заблокированных клеток.
Это countPaths из урока с препятствиями, где заблокированная клетка хранит 0.
Это minPathCost из урока слово в слово.
Каждая позиция приходит из двух позиций над ней, так что заполняй построчно и возьми наименьшее число в последней строке.
Сторона квадрата в клетке равна 1 плюс наименьшее из верхней, левой и верхней левой соседки, на одну соседку больше, чем в уроке.