Q26 Optimal binary search tree | Practice | GeeksforGeeks

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;

class GFG{
    public static void main(String args[])throws IOException
    {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(read.readLine());
        while(t-- > 0)
        {
            int n = Integer.parseInt(read.readLine());
            String input_line[] = read.readLine().trim().split("\\s+");
            int keys[]= new int[n];
            for(int i = 0; i < n; i++)
                keys[i] = Integer.parseInt(input_line[i]);
            String input_line1[] = read.readLine().trim().split("\\s+");
            int freq[]= new int[n];
            for(int i = 0; i < n; i++)
                freq[i] = Integer.parseInt(input_line1[i]);
            Solution ob = new Solution();
            System.out.println(ob.optimalSearchTree(keys, freq, n));
        }
    }
}
// } Driver Code Ends


//User function Template for Java

class Solution
{
    static int optimalSearchTree(int keys[], int frequency[], int n)
    {
        //making 2d dp for gap strategy
        int[][] dp = new int[n][n];
        
        //making prefix sum array
        int psa[] = new int[n] , sum = 0;
        
        for(int i = 0 ; i < n ; i++){
            sum += frequency[i];
            psa[i] = sum;
        }
        
        for(int gap = 0 ; gap < n ; gap ++){
            
            //traversing on gap diagnols
            for(int i = 0 , j = gap ; j < n ;i++, j++){
                
                if(gap == 0)
                dp[i][j] = frequency[i];     //i == j
                
                else if(gap == 1){
                    //i = left node , j = right node
                    int f1 = frequency[i] , f2 = frequency[j];
                    dp[i][j] = Math.min(f1 + 2*f2 , 2*f1 + f2);
                }
                
                else{
                    //freq to be added with left and right
                    int freq =0;
                    // for(int x = i ; x <= j ; x++)
                    // freq += frequency[x];
                    
                    //can also be done through prefix sum array for optimization
                    freq = psa[j] - (i == 0 ? 0 : psa[i-1]);
                    //i = left side , j = right side
                    int min = Integer.MAX_VALUE;
                    for(int k = i ; k <= j ;k++){
                        
                        //if k is at begning it left will be zero and if at end righ will
                        // be zero 
                        int left = k == i ? 0 : dp[i][k-1];
                        int right = k == j ? 0 : dp[k+1][j];
                        
                        min = Math.min(min , left + right + freq);
                    }
                    
                    dp[i][j] = min;
                }
            }
        }
        
        return dp[0][n-1];
    }
}