Code & Func

第39天。

一道动态规划的题目，有点想切钢管的问题。

动规方程如下：

$$ dp[i, j] = \left{ \begin{aligned} \sum_{z=0}^j A[z] & & i = 1\ \underset{ {i-1 \leq t \leq n-1} }{max} { dp[i-1, t] + \frac {\sum_{z=t+1}^n A[z]} {n-t+1} } & & others \end{aligned} \right. $$

1
double largestSumOfAverages(vector<int>& A, int K) {
2
    // vector<vector<double>> dp(K + 1, vector<double>(A.size(), 0));
3
    vector<double> dp(A.size(), 0);
4
    double sum = 0;
5
    int count;
6
    for(int j = 0;j < A.size(); j++) {
7
        sum += A[j];
8
        dp[j] = sum / (j + 1);
9
    }
10
    for(int i = 1;i < K; i++) {
11
        for(int j = A.size() - 1;j >= i; j--) {
12
            sum = 0;
13
            count = 0;
14
            for(int t = j;t >= i; t--) {
15
                sum += A[t];
7 collapsed lines
16
                count++;
17
                dp[j] = max(dp[j], dp[t-1] + sum/count);
18
            }
19
        }
20
    }
21
    return dp[A.size()-1];
22
}