1130. Minimum Cost Tree From Leaf Values

Link

Solution

dp[i][j] = dp[i][k] + dp[k+1][j] + Max(i....k) * Max(k+1...j)

1. How to calculate Max[i][j] , the max value of arr[i] to arr[j]

2. How to iterate the dp[i][j]

  public int mctFromLeafValues(int[] arr) {
        int[][] max = new int[arr.length][arr.length];
        int[][] dp = new int[arr.length][arr.length];
        for(int i = 0; i < arr.length; i++){
            int cmax = 0;
            for(int j = i; j < arr.length; j++){
                cmax = Math.max(cmax, arr[j]);
                max[i][j] = cmax;
            }
        }
        for(int len = 1; len < arr.length; len++){
            for(int left = 0; left + len < arr.length; left++){
                
                int right = left + len;
                if(len == 1){
                    dp[left][right] = arr[left]*arr[right];
                }
                else{
                    int min = Integer.MAX_VALUE;
                    for(int k = left; k < right; k++)
                    {
                        min = Math.min(min, dp[left][k] + dp[k+1][right] + max[left][k] * max[k+1][right]);
                    }
                    dp[left][right] = min;    
                }
            }
        }
        
        
        return dp[0][arr.length-1];
    }