石子合并

一句话理解

石子合并：相邻两堆合并，代价是和，求最小总代价。

为什么要学

区间 DP 经典。

讲解

f[l][r]=min_k f[l][k]+f[k+1][r]+sum(l,r)。前缀和加速 cost。

例子

最后一次一定是左右两段合并。

常见错误

• 环形石子没断环成链。
• sum 每次 O(n) 变成 n^4。