# Maximum Weighted K-Edge Path
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-weighted-k-edge-path)
Canonical: https://scaleengineer.com/dsa/problems/maximum-weighted-k-edge-path
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Hash Table, Graph
---
## Problem
You are given an integer `n` and a **Directed Acyclic Graph (DAG)** with `n` nodes labeled from 0 to `n - 1`. This is represented by a 2D array `edges`, where `edges[i] = [ui, vi, wi]` indicates a directed edge from node `ui` to `vi` with weight `wi`.

You are also given two integers, `k` and `t`.

Your task is to determine the **maximum** possible sum of edge weights for any path in the graph such that:

* The path contains **exactly** `k` edges.
* The total sum of edge weights in the path is **strictly** less than `t`.

Return the **maximum** possible sum of weights for such a path. If no such path exists, return `-1`.

**Example 1:**

**Input:** n = 3, edges = \[\[0,1,1\],\[1,2,2\]\], k = 2, t = 4

**Output:** 3

**Explanation:**

![](https://assets.glich.co/dsa/maximum-weighted-k-edge-path/image0.png)

* The only path with `k = 2` edges is `0 -> 1 -> 2` with weight `1 + 2 = 3 < t`.
* Thus, the maximum possible sum of weights less than `t` is 3.

**Example 2:**

**Input:** n = 3, edges = \[\[0,1,2\],\[0,2,3\]\], k = 1, t = 3

**Output:** 2

**Explanation:**

![](https://assets.glich.co/dsa/maximum-weighted-k-edge-path/image1.png)

* There are two paths with `k = 1` edge:  
  * `0 -> 1` with weight `2 < t`.
  * `0 -> 2` with weight `3 = t`, which is not strictly less than `t`.
* Thus, the maximum possible sum of weights less than `t` is 2.

**Example 3:**

**Input:** n = 3, edges = \[\[0,1,6\],\[1,2,8\]\], k = 1, t = 6

**Output:** \-1

**Explanation:**

![](https://assets.glich.co/dsa/maximum-weighted-k-edge-path/image2.png)

* There are two paths with k = 1 edge:  
  * `0 -> 1` with weight `6 = t`, which is not strictly less than `t`.
  * `1 -> 2` with weight `8 > t`, which is not strictly less than `t`.
* Since there is no path with sum of weights strictly less than `t`, the answer is -1.

**Constraints:**

* `1 <= n <= 300`
* `0 <= edges.length <= 300`
* `edges[i] = [ui, vi, wi]`
* `0 <= ui, vi < n`
* `ui != vi`
* `1 <= wi <= 10`
* `0 <= k <= 300`
* `1 <= t <= 600`
* The input graph is **guaranteed** to be a **DAG**.
* There are no duplicate edges.

# Approaches
## Brute-Force Depth First Search
This approach involves exploring every possible path of length `k` in the graph. We can use a Depth First Search (DFS) traversal starting from each node. The recursion keeps track of the current path's length and total weight.
**Time:** O(n * d^k), where `d` is the average out-degree of nodes. The number of paths of length `k` can be exponential, making this approach infeasible for the given constraints. · **Space:** O(k) for the recursion stack depth.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
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.
### Algorithm
*   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`.

## Dynamic Programming
A more efficient solution uses dynamic programming. This problem exhibits optimal substructure and overlapping subproblems, as the maximum weight path of length `i` can be found by extending maximum weight paths of length `i-1`. This approach is analogous to a `k`-iteration Bellman-Ford algorithm.
**Time:** O(k * E), where `E` is the number of edges. We iterate `k` times, and in each iteration, we process all `E` edges. · **Space:** O(k * n) to store the DP table.
**Pros:** Guaranteed to find the optimal solution.; Efficient enough to pass the given constraints.
**Cons:** Requires O(k * n) space, which can be large if `k` and `n` are big.
### Explanation
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.
```java
import java.util.Arrays;

class Solution {
    public int maxWeightedKEdgePath(int n, int[][] edges, int k, int t) {
        long[][] dp = new long[k + 1][n];
        for (long[] row : dp) {
            Arrays.fill(row, -1);
        }

        for (int j = 0; j < n; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i <= k; i++) {
            for (int[] edge : edges) {
                int u = edge[0];
                int v = edge[1];
                int w = edge[2];
                if (dp[i - 1][u] != -1) {
                    dp[i][v] = Math.max(dp[i][v], dp[i - 1][u] + w);
                }
            }
        }

        long maxWeight = -1;
        for (int j = 0; j < n; j++) {
            if (dp[k][j] != -1 && dp[k][j] < t) {
                maxWeight = Math.max(maxWeight, dp[k][j]);
            }
        }

        return (int) maxWeight;
    }
}
```
### Algorithm
*   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.

## Space-Optimized Dynamic Programming
The standard dynamic programming approach can be optimized in terms of space. Notice that to compute the maximum weights for paths of length `i`, we only need the results for paths of length `i-1`. This allows us to reduce the space complexity from O(k * n) to O(n).
**Time:** O(k * E). The time complexity remains the same as the unoptimized DP approach. · **Space:** O(n). We only need two arrays of size `n` to store the DP states for the current and previous number of edges.
**Pros:** Most memory-efficient solution.; Maintains the same time efficiency as the standard DP approach.
**Cons:** Slightly more complex to implement due to the need to swap or copy arrays in each iteration.
### Explanation
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`.
```java
import java.util.Arrays;

class Solution {
    public int maxWeightedKEdgePath(int n, int[][] edges, int k, int t) {
        long[] dp = new long[n];
        // Base case for 0 edges is implicitly handled as the array is initialized to 0.

        for (int i = 1; i <= k; i++) {
            long[] next_dp = new long[n];
            Arrays.fill(next_dp, -1);
            for (int[] edge : edges) {
                int u = edge[0];
                int v = edge[1];
                int w = edge[2];
                // dp[u] corresponds to the max weight of a path with i-1 edges ending at u.
                if (dp[u] != -1) {
                    next_dp[v] = Math.max(next_dp[v], dp[u] + w);
                }
            }
            dp = next_dp;
        }

        long maxWeight = -1;
        for (long weight : dp) {
            if (weight != -1 && weight < t) {
                maxWeight = Math.max(maxWeight, weight);
            }
        }

        return (int) maxWeight;
    }
}
```
### Algorithm
*   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.