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

執行結果如下：

***