{x}
blog image

Maximum Cost of Trip With K Highways

Solution: State Compression Dynamic Programming

This problem can be efficiently solved using state compression dynamic programming. The constraints (small number of cities, n <= 15) make this approach feasible.

Core Idea:

We represent the visited cities using a bitmask. Each bit in the bitmask corresponds to a city; a bit set to 1 means the city has been visited, and 0 means it hasn't. We use dynamic programming to find the maximum cost to reach a certain state (bitmask) while ending at a particular city.

State Definition:

  • dp[mask][city]: The maximum cost achievable when the visited cities are represented by mask and the last visited city is city.

Base Case:

  • dp[1 << i][i] = 0 for all cities i (starting at each city individually).

Recurrence Relation:

To compute dp[mask][city], we iterate through all previous cities prev_city. If prev_city is in the mask (meaning it was visited before), we check if there's a highway connecting prev_city and city. If so, we update dp[mask][city] with the maximum of its current value and dp[mask ^ (1 << city)][prev_city] + cost(prev_city, city). The mask ^ (1 << city) removes the current city from the mask, giving us the mask of previously visited cities.

Algorithm:

  1. Initialization: Create a DP table dp of size (1 << n) x n, initialized to negative infinity. Set the base cases.
  2. Iteration: Iterate through all possible masks and cities. For each (mask, city) pair:
    • Iterate through all prev_city that are in mask.
    • Check if a highway connects prev_city and city.
    • Update dp[mask][city] if a better cost is found.
  3. Result: Iterate through all masks with k + 1 bits set (representing trips of length k). Find the maximum value in dp for these masks, which is the maximum cost achievable.

Time and Space Complexity:

  • Time Complexity: O(n * 2n * n) = O(n2 * 2n). The outer loop iterates through all possible masks (2n), the second loop iterates through all cities (n), and the inner loop iterates through previous cities (at most n).
  • Space Complexity: O(n * 2n) to store the DP table.

Code (Python):

def maximumCost(n, highways, k):
    if k >= n:
        return -1
 
    graph = defaultdict(list)
    for u, v, cost in highways:
        graph[u].append((v, cost))
        graph[v].append((u, cost))
 
    dp = [([-float('inf')] * n) for _ in range(1 << n)]
    for i in range(n):
        dp[1 << i][i] = 0
 
    for mask in range(1 << n):
        for city in range(n):
            if (mask >> city) & 1:
                for prev_city, cost in graph[city]:
                    if (mask >> prev_city) & 1:
                        dp[mask][city] = max(dp[mask][city], dp[mask ^ (1 << city)][prev_city] + cost)
 
    max_cost = -1
    for mask in range(1 << n):
        if bin(mask).count('1') == k + 1:
            for city in range(n):
                if (mask >> city) & 1:
                    max_cost = max(max_cost, dp[mask][city])
 
    return max_cost
 
from collections import defaultdict

Code (Java): (Similar structure to Python, but using Java's bit manipulation and data structures)

import java.util.*;
 
class Solution {
    public int maximumCost(int n, int[][] highways, int k) {
        if (k >= n) return -1;
 
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        for (int[] h : highways) {
            graph[h[0]].add(new int[]{h[1], h[2]});
            graph[h[1]].add(new int[]{h[0], h[2]});
        }
 
        long[][] dp = new long[1 << n][n];
        for (long[] row : dp) Arrays.fill(row, Long.MIN_VALUE);
        for (int i = 0; i < n; i++) dp[1 << i][i] = 0;
 
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int city = 0; city < n; city++) {
                if ((mask >> city) != 0) {
                    for (int[] edge : graph[city]) {
                        int prev = edge[0];
                        int cost = edge[1];
                        if ((mask >> prev) != 0) {
                            dp[mask][city] = Math.max(dp[mask][city], dp[mask ^ (1 << city)][prev] + cost);
                        }
                    }
                }
            }
        }
 
        long maxCost = -1;
        for (int mask = 0; mask < (1 << n); mask++) {
            int count = Integer.bitCount(mask);
            if (count == k + 1) {
                for (int city = 0; city < n; city++) {
                    if ((mask >> city) != 0) {
                         maxCost = Math.max(maxCost, dp[mask][city]);
                    }
                }
            }
        }
        return (int) maxCost;
    }
}

Other languages (C++, Javascript, etc.) would follow a similar structure. Remember to handle potential integer overflow depending on the input constraints if using int instead of long data types.