[Swift]LeetCode1130. 叶值的最小代价生成树 | Minimum Cost Tre
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given an array?
Among all possible binary trees considered,?return the smallest possible sum of the values of each non-leaf node.? It is guaranteed this sum fits into a 32-bit integer. Example 1: Input: arr = [6,2,4] Output: 32 Explanation: There are two possible trees. The first has non-leaf node sum 36,and the second has non-leaf node sum 32. 24 24 / / 12 4 6 8 / / 6 2 2 4 Constraints:
给你一个正整数数组?
在所有这样的二叉树中,返回每个非叶节点的值的最小可能总和。这个和的值是一个?32 位整数。 示例: 输入:arr = [6,4] 输出:32 解释: 有两种可能的树,第一种的非叶节点的总和为 36,第二种非叶节点的总和为 32。 24 24 / / 12 4 6 8 / / 6 2 2 4 提示:
Runtime:?36 ms
Memory Usage:?20.9 MB
1 class Solution { 2 func mctFromLeafValues(_ arr: [Int]) -> Int { 3 var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:45),count:45) 4 var maxn:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:45) 5 var n:Int = arr.count 6 for i in 0..<n 7 { 8 maxn[i][i] = arr[i] 9 for j in (i + 1)..<n 10 { 11 maxn[i][j] = max(maxn[i][j - 1],arr[j]) 12 } 13 } 14 for d in 2...n 15 { 16 var i:Int = 0 17 while(i + d - 1 < n) 18 { 19 var j:Int = i + d - 1 20 dp[i][j] = (1<<60) 21 for k in i..<j 22 { 23 dp[i][j] = min(dp[i][j],maxn[i][k] * maxn[k+1][j] + dp[i][k] + dp[k + 1][j]) 24 } 25 i += 1 26 } 27 } 28 return (dp[0][n - 1]) 29 } 30 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |