如何使用golang求出将n堆石子合并成一堆的最小得分

本篇内容主要讲解"如何使用golang求出将n堆石子合并成一堆的最小得分"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"如何使用golang求出将n堆石子合并成一堆的最小得分"吧!

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

package mainimport (    "fmt"    "math")func main() {       arr := []int{   1, 4, 2, 3}    ret := StoneMerge(arr)    fmt.Println(ret)}func sum(arr []int) []int {       N := len(arr)    s := make([]int, N+1)    s[0] = 0    for i := 0; i < N; i++ {           s[i+1] = s[i] + arr[i]    }    return s}func w(s []int, l int, r int) int {       return s[r+1] - s[l]}func StoneMerge(arr []int) int {       if len(arr) < 2 {           return 0    }    N := len(arr)    s := sum(arr)    dp := make([][]int, N)    for i := 0; i < N; i++ {           dp[i] = make([]int, N)    }    best := make([][]int, N)    for i := 0; i < N; i++ {           best[i] = make([]int, N)    }    for i := 0; i < N-1; i++ {           best[i][i+1] = i        dp[i][i+1] = w(s, i, i+1)    }    for L := N - 3; L >= 0; L-- {           for R := L + 2; R < N; R++ {               next := math.MaxInt64            choose := -1            for leftEnd := best[L][R-1]; leftEnd <= best[L+1][R]; leftEnd++ {                   cur := dp[L][leftEnd] + dp[leftEnd+1][R]                if cur <= next {                       next = cur                    choose = leftEnd                }            }            best[L][R] = choose            dp[L][R] = next + w(s, L, R)        }    }    return dp[0][N-1]}

执行结果如下：

到此，相信大家对"如何使用golang求出将n堆石子合并成一堆的最小得分"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！