Untitled

public class Main {

    public static int minCost(int a[], int i,
                              int j)
    {
        if (i >= j) {

            // Base case
            // If n = 1 or n = 0
            return 0;
        }

        // Initialize cost to maximum value
        int best_cost = Integer.MAX_VALUE;

        // Iterate through all possible indices
        // and find the best index
        // to combine the subproblems
        for (int pos = i; pos < j; pos++) {

            // Compute left subproblem
            int left = minCost(a, i, pos);

            // Compute right subproblem
            int right = minCost(a, pos + 1, j);

            // Calculate the best cost
            best_cost = Math.min(
                    best_cost,
                    left + right + Combine(a, i, j));
        }

        // Return the answer
        return best_cost;
    }

    public static int Combine(int a[], int i, int j)
    {
        int sum = 0;

        // Calculate the sum from i to j
        for (int l = i; l <= j; l++)
            sum += a[l];

        return sum;
    }
    public static void main(String[] args) {
        int n = 3;
        int a[] = { 4, 6, 8 };

        System.out.println(minCost(a, 0, n - 1));
    }
}