0813.最大平均值和的分组

https://leetcode.cn/problems/largest-sum-of-averages/

方法一：前缀和 + 记忆化搜索

时间复杂度 $O(n^2 \times k)$ ，空间复杂度 $O(n \times k)$ 。


func largestSumOfAverages(nums []int, k int) float64 {
	preSum, n := []int{0}, len(nums)
	for i, v := range nums {
		preSum = append(preSum, preSum[i]+v)
	}
	memo := [101][101]float64{}
	var dfs func(i, k int) float64
	dfs = func(i, k int) float64 {
		if i == n {
			return 0
		} else if k == 1 {
			return float64(preSum[n]-preSum[i]) / float64(n-i)
		} else if memo[i][k] > 0 {
			return memo[i][k]
		}
		ans := 0.0
		for j := i; j < n; j++ {
			t := float64(preSum[j+1]-preSum[i])/float64(j-i+1) + dfs(j+1, k-1)
			if ans < t {
				ans = t
			}
		}
		memo[i][k] = ans
		return ans
	}
	return dfs(0, k)
}