Minimum Cost Tree From Leaf Values - Solution & Explanation

The Dynamic Programming approach aims to construct solutions to smaller instances of the problem and then use these solutions to build solutions for the larger problem. We will use a matrix `dp` where `dp[i][j]` represents the minimum cost to build a tree using the subarray `arr[i]` to `arr[j]`. For each possible subarray, we will calculate the cost of making each element in the range a root and update the `dp` matrix with the minimum values.

This Python solution uses a dynamic programming table `dp` with an auxiliary table `max_leaves` to store the maximum leaf node in any subarray. We iterate over subarray lengths, filling in the `dp` values based on smaller subproblems. We also calculate the minimal cost by considering every possible division `k` of the subarray and taking the minimum.

The Greedy Stack Approach involves using a stack to store leaf values in a manner that we can always efficiently compute the minimum possible non-leaf node sum at each step. By iteratively removing the smaller of the pair between any two adjacent elements and calculating it with its closest neighbor, we minimize the resulting non-leaf node sum, guaranteeing efficiency in computation.

This Python code uses a stack for leaf values, checking and resolving conditions by viewing the last element to improve the resulting non-leaf sum through the stack. We only calculate products amongst necessary consecutive nodes inevitably leading to efficient reductions.

According to the problem description, the values in the array arr correspond one-to-one with the values in the inorder traversal of each leaf node of the tree. We can divide the array into two non-empty sub-arrays, corresponding to the left and right subtrees of the tree, and recursively solve for the minimum possible sum of all non-leaf node values in each subtree.

We design a function dfs(i, j), which represents the minimum possible sum of all non-leaf node values in the index range [i, j] of the array arr. The answer is dfs(0, n - 1), where n is the length of the array arr.

The calculation process of the function dfs(i, j) is as follows:

• If i = j, it means that there is only one element in the array arr[i..j], and there are no non-leaf nodes, so dfs(i, j) = 0.
• Otherwise, we enumerate k \in [i, j - 1], divide the array arr into two sub-arrays arr[i..k] and arr[k + 1..j]. For each k, we recursively calculate dfs(i, k) and dfs(k + 1, j). Here, dfs(i, k) represents the minimum possible sum of all non-leaf node values in the index range [i, k] of the array arr, and dfs(k + 1, j) represents the minimum possible sum of all non-leaf node values in the index range [k + 1, j] of the array arr. So dfs(i, j) = min_{i leq k < j} {dfs(i, k) + dfs(k + 1, j) + max_{i leq t leq k} {arr[t]} max_{k < t leq j} {arr[t]}}.

In summary, we can get:

$ dfs(i, j) = \begin{cases} 0, & if i = j \ min_{i leq k < j} {dfs(i, k) + dfs(k + 1, j) + max_{i leq t leq k} {arr[t]} max_{k < t leq j} {arr[t]}}, & if i < j \end{cases}

In the above recursive process, we can use the method of memoization search to avoid repeated calculations. Additionally, we can use an array g to record the maximum value of all leaf nodes in the index range [i, j] of the array arr. This allows us to optimize the calculation process of dfs(i, j):

dfs(i, j) = \begin{cases} 0, & if i = j \ min_{i leq k < j} {dfs(i, k) + dfs(k + 1, j) + g[i][k] cdot g[k + 1][j]}, & if i < j \end{cases}

Finally, we return dfs(0, n - 1).

The time complexity is O(n^3), and the space complexity is O(n^2). Here, n is the length of the array arr$.

We can change the memoization search in Solution 1 to dynamic programming.

Define f[i][j] to represent the minimum possible sum of all non-leaf node values in the index range [i, j] of the array arr, and g[i][j] to represent the maximum value of all leaf nodes in the index range [i, j] of the array arr. Then, the state transition equation is:

$ f[i][j] = \begin{cases} 0, & if i = j \ min_{i leq k < j} {f[i][k] + f[k + 1][j] + g[i][k] cdot g[k + 1][j]}, & if i < j \end{cases}

Finally, we return f[0][n - 1].

The time complexity is O(n^3), and the space complexity is O(n^2). Here, n is the length of the array arr$.