Maximum Weighted K-Edge Path

• Initialize a global variable max_valid_weight = -1.
• Build an adjacency list representation of the graph from the edges array.
• Define a recursive function dfs(node, k, weight).
• In dfs, if k == 0, check if weight < t and update max_valid_weight = max(max_valid_weight, weight). Then return.
• For each neighbor v of node with edge weight w, call dfs(v, k - 1, weight + w).
• Iterate through each node i from 0 to n-1 and start the search by calling dfs(i, k, 0).
• Return max_valid_weight.

We can model this problem as finding all paths of a specific length. A recursive DFS function, say dfs(u, edges_left, current_weight), can be designed to explore these paths.

• State: The function takes the current node u, the number of edges left to traverse edges_left, and the accumulated weight current_weight.
• Base Case: When edges_left becomes 0, it means we have formed a path with exactly k edges. We then check if its current_weight is strictly less than t. If it is, we compare it with a global maximum weight and update if necessary.
• Recursive Step: For the current node u, the function iterates through all its neighbors v. For each edge (u, v) with weight w, it makes a recursive call dfs(v, edges_left - 1, current_weight + w).
• Initialization: To ensure all possible paths are considered, we must initiate the DFS from every node in the graph, i.e., call dfs(i, k, 0) for all i from 0 to n-1.

This method is exhaustive but computationally very expensive.

• Initialize a 2D array dp[k+1][n] with -1.
• Set the base case: dp[0][j] = 0 for all j from 0 to n-1.
• Loop for i from 1 to k (number of edges):
• Inside, loop through each edge `[u, v, w]` in `edges`:
• If a path of `i-1` edges to `u` exists (`dp[i-1][u] != -1`), update the path to `v`:
• `dp[i][v] = max(dp[i][v], dp[i-1][u] + w)`.
• After the loops, find the maximum value in dp[k] that is less than t.
• Return this maximum value, or -1 if none is found.

We define a 2D DP array, dp[i][j], to store the maximum weight of a path that has exactly i edges and ends at node j.

• State: dp[i][j] = maximum weight of a path with i edges ending at node j.
• Base Case: For a path with 0 edges, the weight is 0. We can consider being at any node j as a 0-length path starting and ending at j. Thus, we initialize dp[0][j] = 0 for all j from 0 to n-1. All other dp entries are initialized to -1 to signify impossibility.
• Recurrence Relation: To compute dp[i][v], we look at all incoming edges (u, v) with weight w. A path of i edges to v can be formed by taking a path of i-1 edges to u and then traversing the edge (u, v). The new weight would be dp[i-1][u] + w. We take the maximum over all such predecessors u. dp[i][v] = max(dp[i][v], dp[i-1][u] + w)
• Iteration: We iterate from i = 1 to k. In each iteration, we loop through all edges (u, v, w) and update dp[i][v] based on dp[i-1][u].
• Final Result: After filling the table, the k-th row, dp[k], contains the maximum weights for all paths of length k. We iterate through dp[k][j] for all j, find the maximum value that is strictly less than t, and return it. If no such value exists, we return -1.

1import java.util.Arrays;2 3class Solution {4    public int maxWeightedKEdgePath(int n, int[][] edges, int k, int t) {5        long[][] dp = new long[k + 1][n];6        for (long[] row : dp) {7            Arrays.fill(row, -1);8        }9 10        for (int j = 0; j < n; j++) {11            dp[0][j] = 0;12        }13 14        for (int i = 1; i <= k; i++) {15            for (int[] edge : edges) {16                int u = edge[0];17                int v = edge[1];18                int w = edge[2];19                if (dp[i - 1][u] != -1) {20                    dp[i][v] = Math.max(dp[i][v], dp[i - 1][u] + w);21                }22            }23        }24 25        long maxWeight = -1;26        for (int j = 0; j < n; j++) {27            if (dp[k][j] != -1 && dp[k][j] < t) {28                maxWeight = Math.max(maxWeight, dp[k][j]);29            }30        }31 32        return (int) maxWeight;33    }34}

• Initialize a 1D array dp of size n with 0s (for paths of length 0).
• Loop for i from 1 to k:
• Create a new array `next_dp` of size `n` and initialize it with -1.
• Loop through each edge `[u, v, w]`:
• If `dp[u]` is not -1, update `next_dp[v] = max(next_dp[v], dp[u] + w)`.
• After processing all edges, replace `dp` with `next_dp`.
• After the main loop, find the maximum value in the final dp array that is less than t.
• Return this maximum value, or -1.

Instead of maintaining the entire k x n DP table, we only need two 1D arrays: one to store the results from the previous step (i-1) and one for the current step (i).

• State: We use two arrays, dp (for step i-1) and next_dp (for step i), both of size n.
• Base Case: The dp array is initialized for 0 edges. dp[j] = 0 for all j.
• Iteration: We loop i from 1 to k. In each iteration:
  1. Initialize next_dp with -1.
  2. Iterate through all edges (u, v, w).
  3. If a path to u existed in the previous step (dp[u] != -1), we update the potential path to v in the current step: next_dp[v] = max(next_dp[v], dp[u] + w).
  4. After iterating through all edges, next_dp contains the results for i edges. We then update dp = next_dp for the next iteration.
• Final Result: After k iterations, the dp array holds the maximum weights for paths of length k. We find the maximum value in this array that is less than t.

1import java.util.Arrays;2 3class Solution {4    public int maxWeightedKEdgePath(int n, int[][] edges, int k, int t) {5        long[] dp = new long[n];6        // Base case for 0 edges is implicitly handled as the array is initialized to 0.7 8        for (int i = 1; i <= k; i++) {9            long[] next_dp = new long[n];10            Arrays.fill(next_dp, -1);11            for (int[] edge : edges) {12                int u = edge[0];13                int v = edge[1];14                int w = edge[2];15                // dp[u] corresponds to the max weight of a path with i-1 edges ending at u.16                if (dp[u] != -1) {17                    next_dp[v] = Math.max(next_dp[v], dp[u] + w);18                }19            }20            dp = next_dp;21        }22 23        long maxWeight = -1;24        for (long weight : dp) {25            if (weight != -1 && weight < t) {26                maxWeight = Math.max(maxWeight, weight);27            }28        }29 30        return (int) maxWeight;31    }32}