2021-02-26：一个数组 arr 是二叉树的中序遍历后果，每条边的开销是父节点和子节点的乘积，总开销是所有边的开销之和。请问最小总开销是多少？
链接：https://www.nowcoder.com/ques…
起源：牛客网
小团有一个由 N 个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团依照二叉树的中序遍历顺次记录下每个节点的权值，即他记录下了 N 个数，第 i 个数示意位于中序遍历第 i 个地位的节点的权值。之后因为某种原因，小团忘记了二叉树的具体构造。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。当初，小团请小美求出最优二叉树的总开销。
输出形容:
第一行输出一个整数 N（1<=N<=300），示意二叉树的节点数。
第二行输出 N 个由空格隔开的整数，示意按中序遍历记录下的各个节点的权值，所有权值均为不超过 1000 的正整数。
输入形容:
输入一个整数，示意最优二叉树的总开销。
福哥答案 2021-02-26：
天然智慧即可。
1. 递归。有代码。
2. 记忆化搜寻。有代码。
代码用 golang 编写，代码如下：
package main
import "fmt"
const MAX = int(^uint(0) >> 1)
//https://www.nowcoder.com/questionTerminal/0d939e874a004f449a370aca1346dd5c
func main() {arr := []int{7, 6, 5, 1, 3}
ret := f1(arr)
fmt.Println("1. 递归：", ret)
ret = f2(arr)
fmt.Println("2. 记忆化搜寻：", ret)
}
func f1(arr []int) int {arrLen := len(arr)
if arrLen <= 1 {return 0}
return process1(arr, -1, 0, arrLen-1)
}
func process1(arr []int, cur int, L int, R int) int {
length := R - L + 1
if length == 0 {return 0}
ans := MAX
for i := L; i <= R; i++ {
temp := 0
if cur >= 0 {temp = arr[cur] * arr[i]
}
ans = getMin(temp+process1(arr, i, L, i-1)+process1(arr, i, i+1, R), ans)
}
return ans
}
func f2(arr []int) int {arrLen := len(arr)
if arrLen <= 1 {return 0}
dp := make([][][]int, arrLen+1)
for i := 0; i < arrLen+1; i++ {dp[i] = make([][]int, arrLen)
for j := 0; j < arrLen; j++ {dp[i][j] = make([]int, arrLen)
for k := 0; k < arrLen; k++ {dp[i][j][k] = -1
}
}
}
ret := process2(arr, -1, 0, arrLen-1, dp)
//fmt.Println(dp)
return ret
}
func process2(arr []int, cur int, L int, R int, dp [][][]int) int {
length := R - L + 1
if length == 0 {return 0}
if dp[cur+1][L][R] != -1 {//fmt.Println("记忆化", dp[cur+1][L][R])
return dp[cur+1][L][R]
}
ans := MAX
for i := L; i <= R; i++ {
temp := 0
if cur >= 0 {temp = arr[cur] * arr[i]
}
ans = getMin(temp+process2(arr, i, L, i-1, dp)+process2(arr, i, i+1, R, dp), ans)
}
dp[cur+1][L][R] = ans
return ans
}
func getMin(a int, b int) int {
if a < b {return a} else {return b}
} 执行后果如下：
评论