题目链接 282. 石子合并
主体思路
用dp[l][r]表示区间[l, r]的石头合成一堆的成本(或者 方法)
区间从小到大开始枚举
知道了区间大小,也就知道了左右两端 l, r,在l, r之间枚举k,求最后一次的dp[l][k] 与 dp[k + 1][r]结合的最小代价
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + n[r] - n[l - 1])
注意细节
记得用前缀和来算任意区间的石头代价
基础代码
package main
import "fmt"
func cal(N int, n []int) int {
var (
min = func(i, j int) int { if i < j { return i }; return j }
dp = make([][]int, N + 1)
)
for i := range dp { dp[i] = make([]int, N + 1) }
for len := 2; len <= N; len++ {
for i := 1; i + len - 1 <= N; i++ {
l, r := i, i + len - 1
dp[l][r] = 1 << 31 - 1
for k := l; k < r; k++ { dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + n[r] - n[l - 1]) }
}
}
return dp[1][N]
}
func main() {
var (
ans int
N, tmp int
n = []int{0}
)
fmt.Scanf("%d", &N)
for i := 1; i <= N; i++ {
fmt.Scanf("%d", &tmp)
n = append(n, tmp)
}
for i := 1; i <= N; i++ { n[i] += n[i - 1] }
ans = cal(N, n)
fmt.Println(ans)
}