Сколько уникальных путей к цели?
Давайте рассмотрим небольшую забавную задачу.
Робот расположен в верхнем левом углу сетки размером m x n, отмечен «Start» на диаграмме ниже).
Робот может двигаться только вниз или вправо в любой момент. Робот пытается добраться до правого нижнего угла сетки, отмеченного на диаграмме ниже «Готово».
Сколько существует возможных уникальных путей?
Выше - сетка 7 х 3. Сколько существует возможных уникальных путей?
Пример 1
- Ввод: m = 3, n = 2
- Выход: 3
- Объяснение: Всего из левого верхнего угла можно попасть в правый нижний угол тремя способами:
- Справа - ›Справа -› Вниз
- Вправо - ›Вниз -› Вправо
- Вниз - ›Справа -› Справа Пример 2:
- Ввод: m = 7, n = 3.
- Выход: 28
- Ограничения: 1 ‹= m, n‹ = 100 Гарантированно, что ответ будет меньше или равен 2 * 10 ^ 9.
Как и в случае с нашей предыдущей проблемой, мы сразу понимаем, что для ее решения следует использовать восходящий подход, поскольку от нас требуется найти все возможные уникальные пути.
Базовый вариант
При любом восходящем подходе нам нужно сначала установить несколько базовых случаев. Я думаю о базовых случаях как о случаях, которые невозможно разбить дальше - это простейшая форма подзадач. Если я могу вычислить их за один шаг, независимо от любых предыдущих результатов, то это должен быть базовый случай. Обычно хорошее начало для поиска базового случая - это посмотреть на наименьший размер входных данных проблемы (то есть крайний случай). В нашем случае это будет m = 1 и n = 1. Итак, сколько уникальных путей, если m = 1 и n = 1. Было бы просто 1.
Хорошо - мы установили базовый вариант. Есть еще?
Помните, что робот может двигаться только вниз или вправо в любой момент времени. Это означает, , что если m = 1, значение n не имеет значения - существует только один уникальный путь, чтобы попасть туда. Точно так же, если n = 1, значение m не имеет значения - опять же, есть только один уникальный путь.
Вау! Этот базовый вариант даже более информативен, чем первый, который мы установили, который является лишь подмножеством этого базового варианта!
Мораль истории: найдите как можно больше базовых случаев, прежде чем пытаться продвигаться вверх
Работаем над
Для случаев, когда m ›1 или n› 1, как мы можем вычислить возможные уникальные пути из наших базовых случаев и предыдущих результатов? Надеюсь, эта часть интуитивно понятна для вас, как и для меня. Потому что для меня было совершенно очевидно, что мы можем вычислить это путем сложения решений двух предыдущих результатов - возможных уникальных путей, идущих слева, и возможных уникальных путей, идущих сверху.
По сути, решение [n] [m] = решение [n-1] [m] + решение [n] [m-1] для всех n, m ›1.
Реализация на Python
Теперь, когда мы знаем, что делать. Давайте реализуем наше решение на Python.
Отлично, мы закончили эту задачу динамического программирования! Как вы думаете, у вас это получается?
