# 1130. Minimum Cost Tree From Leaf Values

[Link](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/)

**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]

```java
  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];
    }
```
