本篇内容主要讲解“如何使用golang求出将n堆石子合并成一堆的最小得分”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“如何使用golang求出将n堆石子合并成一堆的最小得分”吧!
代码用golang编写。代码如下:
package main import ( "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堆石子合并成一堆的最小得分”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。