[动态规划] leetcode 813 Largest Sum of Averages

problem:https://leetcode.com/problems/largest-sum-of-averages

        爬台阶类型dp。递推考虑的不只是从前i个数字到前i + 1个数字，还需要考虑从划分为k到划分为k + 1组，相当于在后面叠加一组。

记忆搜索做法：

class Solution {
public:
    vector<vector<double>> dp;
    double dfs(vector<int>& A, int i, int K)
    {
        if (i == A.size()) return 0.0;
        if (K == 0) return -1;
        if (dp[i][K] >= 0) return dp[i][K];
        double sum = 0;
        double res = 0;
        for (int j = i; j < A.size(); j++)
        {
            sum += A[j];
            int len = j - i + 1;
            double average = dfs(A, j + 1, K - 1);
            if (average >= 0)
            {
                average += sum / len;
                res = max(res, average);
            }
        }
        return dp[i][K] = res;
    }
    double largestSumOfAverages(vector<int>& A, int K) {
        int n = A.size();
        dp.resize(n + 1, vector<double>(K + 1, -1));
        return dfs(A, 0, K);
    }
};      

dp做法：

class Solution {
public:
    vector<vector<double>> dp;
    double largestSumOfAverages(vector<int>& A, int K) {
        int n = A.size();
        dp.resize(n + 1, vector<double>(K + 1));

        double acc = 0;
        vector<double> sums(n, 0);
        for (int i = 0; i < n; i++)
        {
            acc += A[i];
            sums[i] = acc;
            dp[i][1] = acc / (i + 1);
        }
        for (int k = 2; k <= K; k++)
        {
            for (int i = 0; i < n; i++)
            {
                dp[i][k] = dp[i][k - 1];
                for (int j = 0; j < i; j++)
                {
                    int len = i - j;
                    dp[i][k] = max(dp[i][k], dp[j][k - 1] + (sums[i] - sums[j]) / len);
                }
            }
        }
        return dp[n - 1][K];
    }
};      

滚动数组优化空间后的做法：

class Solution {
public:
    vector<double> dp;
    double largestSumOfAverages(vector<int>& A, int K) {
        int n = A.size();
        dp.resize(n + 1);
        
        double acc = 0;
        vector<double> sums(n, 0);
        for (int i = 0; i < n; i++)
        {
            acc += A[i];
            sums[i] = acc;
            dp[i] = acc / (i + 1);
        }
        for (int k = 2; k <= K; k++)
        {
            for (int i = n - 1;i >= 0;i--)
            {
                for (int j = k - 1; j < i; j++)
                {
                    int len = i - j;
                    dp[i] = max(dp[i], dp[j] + (sums[i] - sums[j]) / len);
                }
            }
        }
        return dp[n - 1];
    }
};      

转载于:https://www.cnblogs.com/fish1996/p/11326182.html