813. 最大平均值和的分组

发表于 分类于 阅读次数： Waline： 本文字数： 183 阅读时长 ≈ 1 分钟

考点

  • 划分DP

思路

约束了划分个数的划分DP裸题，注意划分个数只有一个时，是前缀和的特殊情况即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  double largestSumOfAverages(vector<int>& nums, int k) {
    // f[j][i]: 前i个数划分的子数组小于等于j个的最大分数
    double f[105][105];
    // 前缀和打表
    int n = nums.size();
    double pre[105];
    pre[0] = 0;
    for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + nums[i - 1];
    // DP
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) f[0][i] = -1;
    for (int j = 1; j <= k; ++j) {
      for (int r = j; r <= n; ++r) {
        f[j][r] = 0;
        for (int l = j; l <= r; ++l) {
          if (f[j - 1][l - 1] != -1)
            f[j][r] = max(
                f[j][r], f[j - 1][l - 1] + (pre[r] - pre[l - 1]) / (r - l + 1));
        }
      }
    }
    return f[k][n];
  }
};