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]; } };
[动态规划] leetcode 813 Largest Sum of Averages
原文：https://www.cnblogs.com/fish1996/p/11326182.html