2021-04-16：摆放着n堆石子。现要将石子有次序地合并成一堆，规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。求出将n堆石子合并成一堆的最小得分（或最大得分）合并方案。
福大大 答案2021-04-16：
动态规划。
代码用golang编写。代码如下：
代码语言：txt复制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]
}执行结果如下：
图片左神java代码
评论
