题目描述：
给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个非空子数组，且数组内部是连续的 。 分数 由每个子数组内的平均值的总和构成。
注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。
返回我们所能得到的最大 分数 是多少。答案误差在 10-6 内被视为是正确的。
数据范围：
$1\le nums.len \le 100, 1\le nums[i] \le 10^4, 1\le k \le nums.len$
题解：
假设 $dp[i][k]$ 表示将区间 $[1, i]$ 分为 $k$ 个子数组所能得到的最大价值。
则需要枚举上一个区间的右端点，即 $dp[j][k - 1]$ ，然后计算区间 $[j + 1, i]$ 的平均值，该平均值的计算需要用到前缀和。
即
需要注意初始化，初始化每个子数组分成一段的价值，即 $dp[i][1]$ .
先枚举 $k$ ，则 $k \in [2, n], i \in [k, n], j \in [k - 1, i)$
先枚举 $i$ ，则 $i\in [1, n], k \in [2, i], j\in [k-1, i)$
因为 $dp[i][k]$ 只用到了 $dp[][k-1]$ ，也就是只用到了前一列，因此可以考虑优化为一维状态。又因为 $dp[i][k]$ 需要用到前一列前面的，因此优化为一维时，只能对 $i$ 倒着枚举。
代码：
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
double largestSumOfAverages1(vector<int> &nums, int k)
{
int n = nums.size();
vector<int> preSum(n + 1);
for (int i = 1; i <= n; ++i)
{
preSum[i] += preSum[i - 1] + nums[i - 1];
}
vector<vector<double>> dp(n + 1, vector<double>(k + 1));
for (int i = 1; i <= n; ++i)
dp[i][1] = 1.0 * preSum[i] / i;
for (int i = 1; i <= n; ++i)
{
for (int kk = 2; kk <= k; ++kk)
{
for (int j = kk - 1; j < i; ++j)
{
dp[i][kk] = max(dp[i][kk], dp[j][kk - 1] + 1.0 * (preSum[i] - preSum[j]) / (i - j));
}
}
}
return dp[n][k];
}
double largestSumOfAverages(vector<int> &nums, int k)
{
int n = nums.size();
vector<int> preSum(n + 1);
for (int i = 1; i <= n; ++i)
{
preSum[i] += preSum[i - 1] + nums[i - 1];
}
vector<double> dp(n + 1);
for (int i = 1; i <= n; ++i)
dp[i] = 1.0 * preSum[i] / i;
for (int kk = 2; kk <= k; ++kk)
{
for (int i = n; i >= 1; --i)
{
for (int j = kk - 1; j < i; ++j)
{
dp[i] = max(dp[i], dp[j] + 1.0 * (preSum[i] - preSum[j]) / (i - j));
}
}
}
return dp[n];
}
};
|