320、能量项链 - AcWing题库
分析：可以看成一个环形的区间dp问题
一共有4个珠子，如图有四个标记，可以合并到最后只剩下2个标记，也就是1个珠子为止。
那么最少是需要3个标记才可以继续合并，如果小于三个标记就不用再合并了。
状态表示：所有合并i~j个标记的集合
状态计算/划分依据：根据i~j中间的标记可以划分为不重不漏的j-i-1个集合，由于i，j表示的是标记，所以不能参与合并(dp[i][i]不是一个珠子，不参与运算,所以dp[i][j],j>=i+1)
递推公式是dp[i][k]+dp[k][j],因为断点前一个集合k作为尾标记,后一个集合k作为头标记
i+1作为中断点，合并dp[i][i+1],dp[i+1][j]，dp[i][j]=dp[i][i+1]+dp[i+1][j]+w[i]*w[i+1]*w[j]...j-1作为中断点，合并dp[i][j-1],dp[j-1][j]，dp[i][j]=dp[i][j-1]+dp[j-1][j]+w[i]*w[j-1]*w[j]
初始化和边界均为0
递推方式：
for(int len=1;len<=n+1;len++)//由于右端点可能是起点,所以<=n+1//因为最后一个珠子的尾标记是第一个标记 for(int i=1;i+len-1<=2*n;i++) { ... }
ac代码
#include