叶值的最小代价生成树

/*
 * Solution for finding the minimum possible sum of the non-leaf node values in a binary tree
 * using Java Streams. The solution is similar to the dynamic programming approach but uses
 * streams for intermediate calculations.
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class SolutionStream {
    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        int[][] max = new int[n][n];

        // Fill the max array
        IntStream.range(0, n).forEach(i -> {
            max[i][i] = arr[i];
            IntStream.range(i + 1, n).forEach(j -> max[i][j] = Math.max(max[i][j - 1], arr[j]));
        });

        // Fill the dp array
        IntStream.range(2, n + 1).forEach(len -> {
            IntStream.range(0, n - len + 1).forEach(i -> {
                int j = i + len - 1;
                dp[i][j] = IntStream.range(i, j)
                        .map(k -> dp[i][k] + dp[k + 1][j] + max[i][k] * max[k + 1][j])
                        .min().getAsInt();
            });
        });

        return dp[0][n - 1];
    }
}