How hard is LeetCode 1575. Count All Possible Routes?

LeetCode 1575. Count All Possible Routes is rated Hard on LeetCode.

What is the time complexity of LeetCode 1575. Count All Possible Routes?

The Python solution on this page runs in O(n^2 \times m).

What is the space complexity of LeetCode 1575. Count All Possible Routes?

The Python solution on this page uses O(n \times m) auxiliary space.

What topics does LeetCode 1575. Count All Possible Routes cover?

LeetCode 1575. Count All Possible Routes is tagged Memoization, Array and Dynamic Programming on LeetCode.

Count All Possible Routes — LeetCode 1575 Python Solution

HardMemoizationArrayDynamic Programming

Problem: #1575
Pattern: Dynamic Programming
Reading time: 3 min
Source: leetcode.com

The problem

You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.

Example

Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
Output: 4
Explanation: The following are all possible routes, each uses 5 units of fuel:

Python solution

Python

class Solution:
    def countRoutes(
        self, locations: List[int], start: int, finish: int, fuel: int
    ) -> int:
        @cache
        def dfs(i: int, k: int) -> int:
            if k < abs(locations[i] - locations[finish]):
                return 0
            ans = int(i == finish)
            for j, x in enumerate(locations):
                if j != i:
                    ans = (ans + dfs(j, k - abs(locations[i] - x))) % mod
            return ans

        mod = 10**9 + 7
        return dfs(start, fuel)

Complexity

Measure	Complexity
Time	O(n^2 \times m)
Space	O(n \times m) auxiliary

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1575. Count All Possible Routes is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming and Memoization.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1575. Count All Possible Routes?: LeetCode 1575. Count All Possible Routes is rated Hard on LeetCode.
What is the time complexity of LeetCode 1575. Count All Possible Routes?: The Python solution on this page runs in O(n^2 \times m).
What is the space complexity of LeetCode 1575. Count All Possible Routes?: The Python solution on this page uses O(n \times m) auxiliary space.
What topics does LeetCode 1575. Count All Possible Routes cover?: LeetCode 1575. Count All Possible Routes is tagged Memoization, Array and Dynamic Programming on LeetCode.