在尝试搜索算法之前，总是要慎重考虑一下是否ＤＰ可行．特别是本题中求＂最大值＂，有着非常明显的DP的信号.
DP算法的常规动作:考虑元素的逐步递进.对于元素i而言,dp[i]和dp[i-1]有什么关系?对于元素i的处置,无非就是两种:一种就是自个儿单独做为一组;另一种就是和前面若干个元素组成一组.那么到底选择和前面多少个元素捆绑呢?枚举一下就可以了,也就是在[0,i-1]之间找到一个j,使得元素[0,j-1]组成k-1组的平均数之和,加上从[j,i]组成一组的平均数,得到最大值.
由此可见,对于[0,i-1]的DP状态是和k-1有关的.至此,我们可以清楚地知道,DP状态需要设计成dp[i][k],表示A中前i个元素分割成k组时,能得到最大的题意要求的结果.大致的动态转移方程如下:
dp[i][k] = dp[j][k-1] + sum(j+1,k)另外可以发现,这个状态是从较小数量的分割,往较大数量的分割进行的推算.所以外层大循环是组数k,内层循环才是index.
for (k=2; k<K; k++)
for (i=k-1; i<N; i++)
{
dp[i][k] = dp[j][k-1] + sum(j+1,k)
}
边界条件不难看出是k==1时的情况,即需要计算所有的dp[i][1],也就是累加和.