举个栗子吧
假设有 4 堆石子,质量分别为 1, 3, 5, 2。即 n=4,输入数组 s 为 [1,3,5,2]。
s[1] = 1
s[2] = s[1] + 3 = 4
s[3] = s[2] + 5 = 9
s[4] = s[3] + 2 = 11
对于长度为 2 的区间:
f[1][2]=min(f[1][1]+f[2][2]+s[2]−s[0])=4
f[2][3]=min(f[2][2]+f[3][3]+s[3]−s[1])=8
f[3][4]=min(f[3][3]+f[4][4]+s[4]−s[2])=7
对于长度为 3 的区间:
f[1][3]=min(f[1][1]+f[2][3]+s[3]−s[0],f[1][2]+f[3][3]+s[3]−s[0])=min(0+8+9,4+0+9)=13
f[2][4]=min(f[2][2]+f[3][4]+s[4]−s[1],f[2][3]+f[4][4]+s[4]−s[1])=min(0+7+10,8+0+10)=17
对于长度为 4 的区间:
f[1][4]=min(f[1][1]+f[2][4]+s[4]−s[0],f[1][2]+f[3][4]+s[4]−s[0],f[1][3]+f[4][4]+s[4]−s[0])=min(0+17+11,4+7+11,13+0+11)=24