---
# System prepended metadata

title: 1130. Minimum Cost Tree From Leaf Values
tags: [Leetcode, Dynamic Programming, Medium]

---

# 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```。这样的话，就可以得到状态转移方程：
```dp[i][j] = min(dp[i][k]+dp[k+1][j]+max[i][k]*max[k+1][j])```
需要注意，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
```java=
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];
    }
}
```