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

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

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

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

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

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

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

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

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

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

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

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

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

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

Написать комментарий

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

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

Апрель 9, 2023 г.

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

Читать

Игра в камни

Май 27, 2023 г.

Серия задач StoneGame на leetcode - образец игры, где требуется просчитать оптимальную стратегию. Выигрыш/проигрыш начинающего партию предопределен, и второй участник лишь может надеяться на ошибку первого. Но это не наш случай, т.к. по условию ...

Читать

 

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

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



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