1 """ 2 We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve? 3 Note that our partition must use every number in A, and that scores are not necessarily integers. 4 Example: 5 Input: 6 A = [9,1,2,3,9] 7 K = 3 8 Output: 20 9 Explanation: 10 The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20. 11 We could have also partitioned A into [9, 1], [2], [3, 9], for example. 12 That partition would lead to a score of 5 + 2 + 6 = 13, which is worse. 13 """ 14 """ 15 这题目的思想是基于一个事实：一个数组分割之后肯定是份数越多得到的平均值就越大。 16 我们假设dp[i][k]表示为数组A【0~i】分割k份得到的最大平均值。 17 因为最后一个分割点可以出现在任何部分（实际上也得出现在大于k-1个位置之后），所以 18 dp[i][k]=max(dp[i][k], dp[j][k-1]+sum(j~i)/(i-j)) 其中j在j之前的地方j<i, 19 因此可以把这个递推式理解为重新选择最后一个分割点的最大处。 20 当然，要迅速完成sum段求和还需要一个小函数。 21 传送门：https://blog.csdn.net/weixin_37373020/article/details/81543069 22 """ 23 class Solution: 24 def largestSumOfAverages(self, A, K): 25 sums = [0] 26 for a in A: 27 sums.append(sums[-1]+a) #sums[i] = A[0]+A[1]+...A[i-1] 28 def gap_sum(i, j): 29 return sums[j]-sums[i] 30 dp = [[0 for x in range(K+1)] for y in range(len(A)+1)] 31 for i in range(1, len(A)+1): 32 dp[i][1] = gap_sum(0, i)/i 33 for k in range(2, K+1): 34 for i in range(k, len(A)+1): 35 for j in range(i): 36 dp[i][k] = max(dp[i][k], dp[j][k-1]+gap_sum(j, i)/(i-j)) 37 return dp[len(A)][K]