0813.cpp (1260B)
1 2 // Recursive 3 class Solution { 4 static double dp[101][101]; 5 6 public: 7 Solution() { memset(dp, 0xFF, sizeof(dp)); } 8 double largestSumOfAverages(const vector<int> &nums, int k, int c = 0) { 9 if (k == 0) return c == size(nums) ? 0 : -100000; 10 if (dp[k][c] == dp[k][c]) return dp[k][c]; 11 12 double res = 0, sum = 0; 13 for (int i = c, j = 1; i < size(nums); i++, j++) { 14 sum += nums[i]; 15 res = max(res, sum / j + largestSumOfAverages(nums, k - 1, i + 1)); 16 } 17 18 return dp[k][c] = res; 19 } 20 }; 21 22 double Solution::dp[101][101]; 23 24 // Bottom-up DP 25 class Solution { 26 static double dp[101][101]; 27 28 public: 29 double largestSumOfAverages(const vector<int> &nums, int k, int c = 0) { 30 static double sum[101], dp[101]; 31 const int n = size(nums); 32 33 for (int i = 0, acc = 0; i < n; i++) 34 sum[i + 1] = acc += nums[i]; 35 for (int i = 0; i < n; i++) 36 dp[i] = (sum[n] - sum[i]) / (n - i); 37 38 while (--k) { 39 for (int i = 0; i < n; i++) { 40 for (int j = i + 1; j < n; j++) { 41 dp[i] = max(dp[i], dp[j] + (sum[j] - sum[i]) / (j - i)); 42 } 43 } 44 } 45 46 return dp[0]; 47 } 48 };