leetcode 813 - 最大平均和的分组（动态规划）

本文主要是介绍leetcode 813 - 最大平均和的分组（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：https://leetcode-cn.com/problems/largest-sum-of-averages/

我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。

注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。

示例:
输入: 
A = [9,1,2,3,9]
K = 3
输出: 20
解释: 
A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我们也可以把 A 分成[9, 1], [2], [3, 9].
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值。

思路

很显然是个动态规划问题，状态比较好设，重点在找状态转移方程。

• 定义状态：dp[i][k]，表示前i个数分成k组，能获得的最大分数。
• 状态转移方程：
  1）若k=1，只分一组，那么获得的分数就等于sum(A[:i]) / len(A[:i])
  2）若k>1，假设从某个位置j（1 <= j <i）划分，得到一组为A[j]~A[i]，那么剩下k-1组就得从A[0]~A[j-1]中划分得到，每一次划分后得到的分数为dp[j][k-1] + avg(A[j]~A[i])，要获得最大分数，所以有：
  
• 初始化状态：
  1）k=1，则dp[i][1] = sum(A[:i])/len(A[:i]) = sum(A[:i]) / i
  2）i < k，dp[i][k] = dp[i][k-1]
  3）i = k，dp[i][k] = sum(A[:i])

代码

class Solution(object):def largestSumOfAverages(self, A, K):""":type A: List[int]:type K: int:rtype: float""""""dp[i][k] 表示前i个数分成k组能得到的最大分数， 1<=k<=K, 1<=i<=len(A)-1如果k=1，那么dp[i][k] = sum(A[:i])/i如果k>1，假设从某个位置j（1<=j<i)划分，得到一组为A[j]~A[i]，那么剩下k-1组就需要在A[0]~A[j-1]中划分得到，每一次划分后分数为 avg(A[j]~A[i]) + dp[j][k-1]，从中取max，即有状态转移方程：dp[i][k] = max(dp[j][k-1] + avg(A[j]~A[i]))"""n = len(A)dp = [[0] * (K+1) for i in range(n+1)]   # dp[i][k]表示前i个数分成k组能获得的最大分数for i in range(1, n+1):dp[i][1] = float(sum(A[:i])) / i for i in range(1, n+1):for k in range(2, K+1):if k > i:dp[i][k] = dp[i][k-1]elif k == i:dp[i][k] = float(sum(A[:i]))else:dp[i][k] = max([dp[j][k-1] + float(sum(A[j:i]))/(i-j) for j in range(1, i)])return dp[n][K]

时间复杂度固定了，空间复杂度可以减小，类似01背包问题那样，dp[i][k]其实和i没什么关系，把这个维度去掉，用一维dp数组来表示即可。

这篇关于leetcode 813 - 最大平均和的分组（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---