# 1130. Minimum Cost Tree From Leaf Values
###### tags: `Leetcode` `Dynamic Programming` `Medium`
Link: https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
## 思路
比较容易想到的解法就是区间型的DP。令状态```dp[i][j]```表示将```[i,j]```之间的元素最终聚成一个元素所需要的cost。显然，突破点就是如何将这个区间划分为左右两个分支，这就需要遍历可能的内部分界点```k```。这样的话，就可以得到状态转移方程：

需要注意，max[i][j]需要提前处理，这可能需要设计另外一个dp过程：```max[i][j] = Math.max(max[i+1][j-1], Math.max(arr[i], arr[j]));```
或者也可以把两个dp过程放在一起(删掉line20-25 保留line33)
## Code

class Solution {
public int mctFromLeafValues(int[] arr) {
int n = arr.length;
int[][] max = new int[n][n];
int[][] dp = new int[n][n];
for(int i=0; i<n; i++){
max[i][i] = arr[i];
}

for(int len=2; len<=n; len++){
for(int i=0; i+len-1<n; i++){
int j = i+len-1;
max[i][j] = Math.max(max[i+1][j-1], Math.max(arr[i], arr[j]));
}
}

for(int len=2; len<=n; len++){
for(int i=0; i+len-1<n; i++){
int j = i+len-1;
dp[i][j] = Integer.MAX_VALUE;
for(int k=i+1; k<=j; k++){
dp[i][j] = Math.min(dp[i][j], dp[i][k-1]+dp[k][j]+max[i][k-1]*max[k][j]);
// max[i][j] = Math.max(max[i][k-1], max[k][j]);
}
}
}
return dp[0][n-1];
}
}