题目内容

年夜饭的圆桌上摆了 $n$ 盘凉菜（$n$ 至少为 $2$），按顺时针编号为 $0..n-1$，第 $i$ 盘的份量为 $weights[i]$。菜盘围成一圈：$0$ 号与 $n-1$ 号相邻。

每次操作必须选当前相邻的两盘凉菜合并成一盘：

• 新盘份量等于两盘份量之和
• 本次操作的代价等于新盘份量
• 合并后，新盘占据原来两盘的位置，继续与两侧相邻

不断合并，直到桌上只剩一盘凉菜。请计算：完成合并的最小总代价。

请实现：

minCircleMerge(weights: int[]) -> long

输入描述

一行整型数组，形如 $[1, 1, 1]$。

约束：

• $2 \le weights.length \le 400$
• $1 \le weights[i] \le 100$

输出描述

一行整数：最小总代价。

样例1

输入：

[1, 1, 1]

输出：

5

说明：

• 先合并任意两盘，代价 $2$，桌上变为份量 $2$ 与 $1$ 的两盘
• 再合并，代价 $3$
• 总代价 $2+3=5$

样例2

输入：

[1, 2, 3, 4]

输出：

19

说明：

• 一种最优顺序：先合并 $1$ 与 $2$（代价 $3$），环上变为 $[3, 3, 4]$
• 再合并两个 $3$（代价 $6$），变为 $[6, 4]$
• 最后合并（代价 $10$）
• 总代价 $3+6+10=19$

样例3

输入：

[10, 20]

输出：

30

说明：只剩两盘时只能合并一次，代价为 $10+20=30$。