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

福大大架构师每日一题 · · 622 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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 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
    }
}

执行结果如下:


在这里插入图片描述

评论


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

622 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传