Задача: подсчета кол-ва возможных маршрутов

Решаем задачу с литкода №1575 Count All Possible Routes.

Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым можно добраться до города-назначения, при заданном запасе топлива.

Перемещение между городами стоит некоторых затрат топлива. В данной задаче указывается, что затраты топлива определяются модулем разницы между числами, описывающими пару городов.

Также говориться, что можно неоднократно посещать города, включая начальный и конечный пункт, пока есть топливо.

Более классический вариант этой задачи исключает последнее требование, т.е. посещать города можно только один раз. Рассмотрим сначала классику, а затем вернемся к leetcode.

Решение (классический вариант)

Напрашивается использование рекурсии, где на каждой итерации мы исключаем посещенный город, а также уменьшаем запас топлива. Оставшиеся города рассматриваем как кандидатов для продолжения маршрута. И подсчитываем сумму маршрутов.

Рекурсия останавливается, если топлива не хватало для того, чтобы достигнуть очередной локации (вернем ноль). Если достигнута точка назначения, то вернем единицу.

Классика помогает понять принцип решения данной задачи. Очевидно также, что тут нужно использовать мемоизацию для ускорения вычислений. Мы это сделаем в следующем решении.

Решение (задача с литкода)

Суть решения точно такая же, только локации мы можем посещать много раз.

Если локация совпала с конечной, то счетчик стартует не с нуля, а с единицы. Вот и всё отличие.

Теперь добавим требование «вернуть число не более чем 1e9+7» и щепотку оптимизации :).

Мало букафф? Читайте есчо !

GreyCode генератор

Май 3, 2023 г.

Задачи с бинарными последовательностями мне очень нравятся из-за их "эвристичности". Решение часто скрывается в двух шагах, но додуматься не просто. Следующая задача описывается так - нужно сгенерировать n-разрядный "серый код". Если вы не ...

Читать

Задача о неперекрывающихся интервалах

Июнь 7, 2023 г.

Задачи об интервалах легко решаются перебором. Но если элементов много, то нужно сообразить в каком порядке их лучше перебирать, чтобы избежать лишних вычислений. Формулируется задача так: дан массив интервалов, каждый из которых определен двумя числами ...

Читать

Решение задачи оптимизации в направленном графе

Апрель 9, 2023 г.

Сегодня расскажу о решении задачи №1857 с литкода, которая называется как "Largest Color Value in a Directed Graph". Суть задачи: дан направленный ...

Читать

Декодировка строки

Апрель 30, 2023 г.

Задача 394 с литкода. Дана строка, где присутствуют группы вроде N[string], нужно раскрыть скобки, повторяя строку внутри скобок N раз. Структуры могут быть вложенными. Чтобы выработать решение, рассмотрим пример: [crayon-68f91abb09ec8400527247/] ...

Читать
 

Комментарии к «Задача: подсчета кол-ва возможных маршрутов»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: