您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“如何使用golang求出將n堆石子合并成一堆的最小得分”,感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“如何使用golang求出將n堆石子合并成一堆的最小得分”吧!
代碼用golang編寫(xiě)。代碼如下:
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] }
執(zhí)行結(jié)果如下:
到此,相信大家對(duì)“如何使用golang求出將n堆石子合并成一堆的最小得分”有了更深的了解,不妨來(lái)實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún),關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。