leetcode1130 Minimum Cost Tree From Leaf Values

思路：

区间dp。

实现：

 1 class Solution
 2 {
 3 public:
 4     int mctFromLeafValues(vector<int>& arr)
 5     {
 6         int n = arr.size();
 7         vector<vector<int>> maxn(n, vector<int>(n, 0));
 8         for (int i = n - 1; i >= 0; i--)
 9         {
10             for (int j = i; j < n; j++)
11             {
12                 if (j == i) maxn[i][j] = arr[i];
13                 else
14                 {
15                     maxn[i][j] = max(maxn[i][j - 1], arr[j]);
16                 }
17             }
18         }
19         vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
20         for (int i = n - 1; i >= 0; i--)
21         {
22             for (int j = i; j < n; j++)
23             {
24                 if (j == i) dp[i][j] = arr[i];
25                 else if (j == i + 1) dp[i][j] = arr[i] * arr[j];
26                 else
27                 {
28                     dp[i][j] = min(dp[i][j], dp[i + 1][j] + arr[i] * maxn[i + 1][j]);
29                     dp[i][j] = min(dp[i][j], dp[i][j - 1] + arr[j] * maxn[i][j - 1]);
30                     for (int k = i + 1; k < j - 1; k++)
31                     {
32                         dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + maxn[i][k] * maxn[k + 1][j]);
33                     }
34                 }
35             }
36         }
37         return dp[0][n - 1];
38     }
39 }