题目描述
We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?
Note that our partition must use every number in A, and that scores are not necessarily integers.
Example:
Input:
A = [9,1,2,3,9]
K = 3
Output: 20
Explanation:
The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
Note:
1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
Answers within 10^-6 of the correct answer will be accepted as correct.
思路
dp[i][k] 表示从 0 到 i 前 i+1 个元素，分成k组，平均值之和的最大值。
遍历数组，对于前i个元素，遍历 k-1和k的划分位置j, dp[i][k] = max(dp[i][k], dp[j-1][k-1]+avg(j, i)) ，找的最大值。
这个思路好像做过。。
一看就会，一做就不会。。
什么情况。。。
代码
class Solution {
public:
double largestSumOfAverages(vector<int>& A, int K) {
int n = A.size();
vector<vector<double> > dp(n+1, vector<double>(K+1, 0));
vector<int> sum(n+1, 0);
sum[0] = A[0];
for (int i=1; i<n; ++i) {
sum[i] = sum[i-1] + A[i];
}
for (int i=0; i<n; ++i) {
dp[i][1] = sum[i] * 1.0 / (i+1);
for (int k=2; k<=K && k<=i+1; ++k) {
for (int j=1; j<=i; ++j) {
dp[i][k] = max(dp[i][k], dp[j-1][k-1] + (sum[i]-sum[j-1])*1.0 / (i-j+1));
}
}
}
return dp[n-1][K];
}
};