Your question is Memoization for Redundant Computation. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Tesla Supercharger route planning can represent possible charging transitions as a directed acyclic graph. Given this graph, count how many distinct directed routes exist from a starting station to a destination station. A naive recursive implementation repeatedly counts the same downstream subgraphs, so optimize the calculation with memoization or bottom-up dynamic programming.
Each directed edge represents one valid transition. Distinct edge sequences are distinct routes. Return the result modulo 1,000,000,007.
Implement count_routes(graph, start, destination), where graph[i] is a list of station indices reachable directly from station i. Return an integer containing the number of directed routes from start to destination. The empty route counts as one route when start == destination.
The graph is guaranteed to be a DAG, and it contains no duplicate edges.
def count_routes(graph, start, destination):