1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int mctFromLeafValues(int[] arr) {
int n = arr.length;
int[][] dp = new int[n + 1][n + 1];
int[][] max = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
int maxValue = arr[i - 1];
for (int j = i; j <= n; j++) {
maxValue = Math.max(maxValue, arr[j - 1]);
max[i][j] = maxValue;
if (i != j) {
dp[i][j] = Integer.MAX_VALUE;
}
}
}
for (int l = 1; l < n; l++) {
for (int i = 1; i + l <= n; i++) {
int j = i + l;
for (int k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + max[i][k] * max[k + 1][j]);
}
}
}
return dp[1][n];
}
}
|
