Решаем задачу с литкода №1575 Count All Possible Routes.
Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым можно добраться до города-назначения, при заданном запасе топлива.
Перемещение между городами стоит некоторых затрат топлива. В данной задаче указывается, что затраты топлива определяются модулем разницы между числами, описывающими пару городов.
Также говориться, что можно неоднократно посещать города, включая начальный и конечный пункт, пока есть топливо.
Более классический вариант этой задачи исключает последнее требование, т.е. посещать города можно только один раз. Рассмотрим сначала классику, а затем вернемся к leetcode.
Решение (классический вариант)
Напрашивается использование рекурсии, где на каждой итерации мы исключаем посещенный город, а также уменьшаем запас топлива. Оставшиеся города рассматриваем как кандидатов для продолжения маршрута. И подсчитываем сумму маршрутов.
Рекурсия останавливается, если топлива не хватало для того, чтобы достигнуть очередной локации (вернем ноль). Если достигнута точка назначения, то вернем единицу.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
function countRoutes_dontVisitTheSame(locations: number[], start: number, finish: number, fuel: number): number { const combs = (last: number, fuel: number): number => { // топлива не хватило if (fuel < 0) return 0; // достигли точки назначения if (last == finish) return 1; // отмечаем локацию как посещенную const lastWeight = locations[last]; locations[last] = 0; // считаем число маршрутов let count = 0; for (let i = 0; i < locations.length; i++) { // посещенные локации пропускаем if (locations[i] == 0) continue; count += combs(i, fuel - Math.abs(lastWeight - locations[i])) } // восстанавливаем локацию при выходе из функции locations[last] = lastWeight; return count; } return combs(start, fuel) }; |
Классика помогает понять принцип решения данной задачи. Очевидно также, что тут нужно использовать мемоизацию для ускорения вычислений. Мы это сделаем в следующем решении.
Решение (задача с литкода)
Суть решения точно такая же, только локации мы можем посещать много раз.
Если локация совпала с конечной, то счетчик стартует не с нуля, а с единицы. Вот и всё отличие.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function countRoutes(locations: number[], start: number, finish: number, fuel: number): number { const combs = (last: number, fuel: number): number => { // не хватило топлива if (fuel < 0) return 0; // подсчет вариантов let count = 0; // мы достигли точки назначения, но // топливо еще есть, увеличиваем count if (last == finish) count ++; for (let i = 0; i < locations.length; i++) { // пропускаем текущую локацию if (i == last) continue; count += combs(i, fuel - Math.abs(locations[last] - locations[i])) } return count; } return combs(start, fuel) }; |
Теперь добавим требование «вернуть число не более чем 1e9+7» и щепотку оптимизации :).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
function countRoutes(locations: number[], start: number, finish: number, fuel: number): number { // граничные условия позволяют упаковать входные параметры // задачи в одно целое число (key), // потому мы можем использовать "плоскую" карту const cache: Map<number, number> = new Map(), mod = 1e9 + 7; const combs = (last: number, fuel: number): number => { if (fuel < 0) return 0; // смотрим решения в кеше const key = last * 1000 + fuel let value = cache.get(key) if (value !== undefined) return value; // немного оптимизируем вычисления const lastWeight = locations[last]; // считаем варианты let count = 0; if (last == finish) count ++; for (let i = 0; i < locations.length; i++) { if (i == last) continue; count += combs(i, fuel - Math.abs(lastWeight - locations[i])) } // сохраняем значения в кеше cache.set(key, count % mod); return count % mod; } return combs(start, fuel) }; |