LC.813. Largest Sum of Averages

class Solution1(object):
    def largestSumOfAverages(self, A, K):
        """
        dp[i][j] 表示A[:i]最多j+1次分组的最大平均值
        dp[i][j] 可以分成两个部分 dp[p][j-1] 和 一个组 A[p:i]
        python3 和python2 的结果不一样
        """
        dp = [[0] * len(A) for i in range(K)]
        count = 0
        for j in range(len(A)):
            count += A[j]
            dp[0][j] = count/(j+1)
        for i in range(K):
            dp[i][i] = sum(A[:i+1])
        # for line in dp:
        #     print(line)

        # 表示用多少个框， 一个框的时候已经初始化了，所以直接从1开始
        for i in range(1, K):
            # 保证元素数比框数大，因为dp[i][i]已经初始过了，所以从i+1开始
            for j in range(i+1, len(A)):
                # p 少一个框对应的A[:p+1]子数组
                for p in range(i-1, j):
                    dp[i][j] = max(dp[i][j], dp[i-1][p] + sum(A[p+1:j+1])/(j-p))

        return dp[-1][-1]


class Solution(object):
    def largestSumOfAverages(self, A, K):
        """
        带有memory 的递归，
        1.首先子问题得有个return 的过程，即不能在递归结束的时候去和全局变量进行比较。
        2.子问题要和前面的问题相独立，不能讲前面问题的变量传入到子问题中
        """
        self.res = 0
        self.memo = {}
        return self.DFS(0, K, A)


    def DFS(self, start_index, K, A):
        if K == 1:
            average = sum(A[start_index:])/(len(A) - start_index)
            return average
        else:
            key = str(start_index) + "-" + str(K)
            if key not in self.memo:
                sumer, count = 0, 0
                maxer = 0
                for index in range(start_index, len(A) - K+1):
                    sumer, count =  sumer+A[index], count+1
                    maxer = max(maxer, sumer/count + self.DFS(index+1, K-1, A))
                self.memo[key] = maxer
            return  self.memo[key]