文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 DP
    • 2.2 單調(diào)棧貪心

1. 題目

給你一個(gè)正整數(shù)數(shù)組 arr，考慮所有滿足以下條件的二叉樹：

• 每個(gè)節(jié)點(diǎn)都有 0 個(gè)或是 2 個(gè)子節(jié)點(diǎn)。
• 數(shù)組 arr 中的值與樹的中序遍歷中每個(gè)葉節(jié)點(diǎn)的值一一對(duì)應(yīng)。（知識(shí)回顧：如果一個(gè)節(jié)點(diǎn)有 0 個(gè)子節(jié)點(diǎn)，那么該節(jié)點(diǎn)為葉節(jié)點(diǎn)。）
• 每個(gè)非葉節(jié)點(diǎn)的值等于其左子樹和右子樹中葉節(jié)點(diǎn)的最大值的乘積。

在所有這樣的二叉樹中，返回每個(gè)非葉節(jié)點(diǎn)的值的最小可能總和。
這個(gè)和的值是一個(gè) 32 位整數(shù)。

示例： 輸入：arr = [6,2,4] 輸出：32 解釋： 有兩種可能的樹， 第一種的非葉節(jié)點(diǎn)的總和為 36， 第二種非葉節(jié)點(diǎn)的總和為 32。24 24/ \ / \12 4 6 8/ \ / \ 6 2 2 4提示： 2 <= arr.length <= 40 1 <= arr[i] <= 15 答案保證是一個(gè) 32 位帶符號(hào)整數(shù)，即小于 2^31。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

2.1 DP

類似題目：
LeetCode 1039. 多邊形三角剖分的最低得分（區(qū)間DP）

• 區(qū)間DP，見注釋

class Solution { public:int mctFromLeafValues(vector<int>& arr) {int n = arr.size();vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>(n, {INT_MAX, 0}));//dp[i][j] 表示區(qū)間 [i,j] 的 {非葉節(jié)點(diǎn)的min(sum), 區(qū)間的最大葉子節(jié)點(diǎn)值}for(int i = 0; i < n; i++) //初始化{dp[i][i].first = 0;//sumdp[i][i].second = arr[i];//maxval}for(int len = 1; len < n; ++len)//區(qū)間長(zhǎng)度{for(int i = 0, j; i+len < n; ++i)//左端點(diǎn){j = i+len;//右端點(diǎn)for(int k = i; k < j; ++k)//枚舉中間端點(diǎn){if(dp[i][j].first > dp[i][k].first+dp[k+1][j].first+dp[i][k].second*dp[k+1][j].second){ //左區(qū)間的和 + 右區(qū)間的和 + 當(dāng)前節(jié)點(diǎn)的val = maxL*maxRdp[i][j].first = dp[i][k].first+dp[k+1][j].first+dp[i][k].second*dp[k+1][j].second;//用更小的sum更新dp[i][j].second = max(dp[i][k].second, dp[k+1][j].second);// 更新區(qū)間的最大葉節(jié)點(diǎn)值}}}}return dp[0][n-1].first;} };

16 ms 9.3 MB

2.2 單調(diào)棧貪心

• 維護(hù)單調(diào)遞減棧，讓一個(gè)數(shù)字跟其相鄰的2個(gè)數(shù)字中的較小的相乘

class Solution { public:int mctFromLeafValues(vector<int>& arr) {int n = arr.size(), tp, ans = 0;stack<int> stk;stk.push(INT_MAX);for(int a : arr){while(a >= stk.top())//單調(diào)遞減棧，不滿足了，彈棧{tp = stk.top();stk.pop();ans += tp*min(a, stk.top());}stk.push(a);}while(stk.size() > 2){tp = stk.top();stk.pop();ans += tp*stk.top();}return ans;} };

0 ms 8.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1130. 叶值的最小代价生成树（区间DP/单调栈贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。