leetcode 813- dp +递归

这个题的知识点很多呀，分割组块。最终用二维dp进行递归。

图片.png

• code:

double LSA(vector<int>& a, int n, int k, vector<vector<double>>& dp, vector<double> sum_) {
    if (dp[k][n] > 0)
        return dp[k][n];
    if (k == 1)
        return sum_[n] / (n + 1);
    for (int i = 0; i < n; i++) {
        dp[k][n] = max(dp[k][n], LSA(a, i, k - 1,dp,sum_) + (sum_[n] - sum_[i]) / (n - i));
    }
    return dp[k][n];
}
double largestSumOfAverages(vector<int>& A, int K) {
    vector<double> sum_(A.begin(),A.end());
    for (int i = 1; i < A.size(); i++)
        sum_[i] = sum_[i - 1] + A[i];
    vector<vector<double>> dp(K+1, vector<double>(A.size(), 0.0));
    return LSA(A, A.size()-1, K,dp,sum_);
}