1130. Minimum Cost Tree From Leaf Values (區間型

區間型

T: O(n^3)

```java
class Solution {
    public int mctFromLeafValues(int[] arr) {
        Map<String, Integer> memo = new HashMap<>();
        return dfs(arr, 0, arr.length - 1, memo);
    }

    private int dfs(int[] nums, int i, int j, Map<String, Integer> memo) {
        String key = i + "," + j;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        if (i >= j) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for (int k = i; k < j; k++) {
            int cost = maxRemainNumber(nums, i, k) * maxRemainNumber(nums, k + 1, j);
            res = Math.min(res, dfs(nums, i, k, memo) + dfs(nums, k + 1, j, memo) + cost);
        }
        memo.put(key, res);
        return res;
    }

    private int maxRemainNumber(int[] nums, int start, int end) { // i= 0. 1 2 j = 3
        int maxVal = Integer.MIN_VALUE;
        for (int i = start; i <= end; i++) {
            maxVal = Math.max(maxVal, nums[i]);
        }
        return maxVal;
    }
}
```