2547.Minimum-Cost-to-Split-an-Array

很明显这是一个动态规划。我们令dp[i]表示前i个元素进行分组能够得到的最大值。我们关注截止到i为止最后一个分组的区间，故遍历一个变量j从i往前走一遍，则有dp[i]=dp[j-1]+score[j:i]。注意到移动j的过程中，score[j:i]可以用o(1)的时间得到更新。算法的整体时间复杂度就是o(n^2)。