top_down.py

from functools import lru_cache
class Solution:
    def largestSumOfAverages(self, a: List[int], k: int) -> float:
        cusum = list(itertools.accumulate([0]+a))
        @lru_cache(None)
        def dp(i, k):
            #if i>=len(a):return 0
            if k == 1:return (cusum[-1]-cusum[i])/(len(a)-i)
            return max((cusum[j+1]-cusum[i])/(j-i+1) + dp(j+1, k-1) for j in range(i, len(a)-k+1))
        
        return dp(0, k)