動态規劃之最大平均值和的分組

leetcode 813. 最大平均值和的分組

我們将給定的數組 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, 但不是最大值.
           

說明:

1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
答案誤差在 10^-6 内被視為是正确的。
           

思路

使用動态規劃，

dp[i][k]

表示前

i

個數分成

k

組的最大分數

那麼狀态轉移方程為：

dp[i][k] = max(dp[i][k], dp[j][k - 1] + (s[i] - s[j]) / (i - j))

其中

s[i]

表示前

i

個數的和，也即，目前最大值可以由前面

k-1

組的均值加上目前第

k

組的均值遞推得出

base情況是隻有一組的情況，就依次求解均值即可，

dp[i][1] = s[i] / i

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = [[0] * (K + 1) for _ in range(n + 1)]
        s = [0] * (n + 1)
        # 基礎情況
        for i in range(1, n + 1):　# 第一個數對應索引0，注意索引問題
            s[i] = s[i - 1] + A[i - 1]　# 累加和
            dp[i][1] = s[i] / i 　# 前i個分為一組的均值
        
        for i in range(1, n + 1):
            for k in range(2, K + 1):
                for j in range(i):
                    dp[i][k] = max(dp[i][k], dp[j][k - 1] + (s[i] - s[j]) / (i - j))
        return dp[-1][-1]