2021-02-26：一个数组arr是二叉树的中序遍历结果，每条边的开销是父节点和子节点的乘积，总开

2021-02-26：一个数组arr是二叉树的中序遍历结果，每条边的开销是父节点和子节点的乘积，总开销是所有边的开销之和。请问最小总开销是多少？

链接：https://www.nowcoder.com/questionTerminal/0d939e874a004f449a370aca1346dd5c
来源：牛客网

小团有一个由N个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团按照二叉树的中序遍历依次记录下每个节点的权值，即他记录下了N个数，第i个数表示位于中序遍历第i个位置的节点的权值。之后由于某种原因，小团遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小团请小美求出最优二叉树的总开销。

输入描述:
第一行输入一个整数N（1<=N<=300），表示二叉树的节点数。
第二行输入N个由空格隔开的整数，表示按中序遍历记录下的各个节点的权值，所有权值均为不超过1000的正整数。

输出描述:
输出一个整数，表示最优二叉树的总开销。

福哥答案2021-02-26：

自然智慧即可。
1.递归。有代码。
2.记忆化搜索。有代码。

代码用golang编写，代码如下：

package mainimport "fmt"const MAX = int(^uint(0) >> 1)//https://www.nowcoder.com/questionTerminal/0d939e874a004f449a370aca1346dd5cfunc 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    }}

执行结果如下：

每一份赞赏源于懂得

赞赏

0人进行了赞赏支持

每一份赞赏源于懂得

更多相关文章

随机推荐