Watch 10 video solutions for Maximum Cost of Trip With K Highways, a hard level problem involving Dynamic Programming, Bit Manipulation, Graph. This walkthrough by Greg Hogg has 367,056 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A series of highways connect n cities numbered from 0 to n - 1. You are given a 2D integer array highways where highways[i] = [city1i, city2i, tolli] indicates that there is a highway that connects city1i and city2i, allowing a car to go from city1i to city2i and vice versa for a cost of tolli.
You are also given an integer k. You are going on a trip that crosses exactly k highways. You may start at any city, but you may only visit each city at most once during your trip.
Return the maximum cost of your trip. If there is no trip that meets the requirements, return -1.
Example 1:
Input: n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], k = 3 Output: 17 Explanation: One possible trip is to go from 0 -> 1 -> 4 -> 3. The cost of this trip is 4 + 11 + 2 = 17. Another possible trip is to go from 4 -> 1 -> 2 -> 3. The cost of this trip is 11 + 3 + 3 = 17. It can be proven that 17 is the maximum possible cost of any valid trip. Note that the trip 4 -> 1 -> 0 -> 1 is not allowed because you visit the city 1 twice.
Example 2:
Input: n = 4, highways = [[0,1,3],[2,3,2]], k = 2 Output: -1 Explanation: There are no valid trips of length 2, so return -1.
Constraints:
2 <= n <= 151 <= highways.length <= 50highways[i].length == 30 <= city1i, city2i <= n - 1city1i != city2i0 <= tolli <= 1001 <= k <= 50Problem Overview: You are given an undirected graph where cities are connected by highways with a cost. The goal is to choose a trip that uses exactly k highways and produces the maximum total cost, without revisiting cities in the same trip.
Approach 1: Backtracking / DFS Enumeration (Exponential Time)
Start a DFS from every city and explore all possible paths up to length k. Maintain a visited set so the same city is not used twice in a single path. At each step, iterate through neighboring cities and accumulate the highway cost. When the path length reaches k, update the global maximum. This approach explores nearly all permutations of length k, giving a time complexity around O(n * n^k) in dense graphs and O(k) recursion stack space. It works for very small graphs but quickly becomes infeasible as n grows.
Approach 2: State Compression Dynamic Programming (Bitmask DP) (O(2^n * n^2))
The constraint that cities cannot repeat suggests representing visited cities using a bitmask. Define dp[mask][u] as the maximum cost of a trip that visits the set of cities represented by mask and ends at city u. Iterate through all masks and attempt transitions to neighboring cities v that are not yet in the mask. If a highway u → v exists, update dp[mask | (1 << v)][v] with the accumulated cost.
The number of highways used equals bitcount(mask) - 1. Only states where the number of highways equals k are valid final trips. While iterating over states, expand paths until the mask size reaches k + 1 cities. Track the maximum cost among all valid states. Because each mask contains at most n cities and transitions check neighbors, the time complexity becomes O(2^n * n^2) with O(2^n * n) space.
This technique is called state compression because the visited set is encoded in an integer bitmask instead of a collection structure. It is commonly used in problems combining dynamic programming, bitmasking, and graph traversal.
Recommended for interviews: Interviewers expect the state compression DP solution. Brute force DFS demonstrates that you understand the path exploration aspect, but the optimal answer requires recognizing that the visited-city constraint fits naturally into a bitmask representation. Building dp[mask][node] and expanding states efficiently shows strong problem‑solving skills with graph DP.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking / DFS Path Enumeration | O(n * n^k) | O(k) | Small graphs or when exploring all paths conceptually before optimizing |
| State Compression Dynamic Programming (Bitmask DP) | O(2^n * n^2) | O(2^n * n) | Optimal solution for n ≤ 15 graphs where cities cannot repeat |