題目

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

題解

好久不 dp 了，來一道快樂的 dp 保持手感。

經典的暴力遞歸 -> 傻緩存 -> dp，竟然有點手生…

class Solution {public double largestSumOfAverages(int[] nums, int k) {// Solution 1: 帶緩存的暴力遞歸double[][] dp = new double[nums.length + 1][k + 1];for (double[] d : dp) {Arrays.fill(d, Integer.MIN_VALUE);}for (int j = 0; j <= k; j++) {dp[nums.length][j] = -1;} // return process(nums, 0, k, dp);// Solution 2: 自底向上的dpfor (int i = nums.length; i >= 0; i--) { // from index ifor (int p = 1; p <= k; p++) { // p partitionif (p == 1) {double sum = 0;for (int j = i; j < nums.length; j++) {sum += nums[j];}dp[i][p] = sum / (nums.length - i);}double result = -1;double preSum = 0;for (int j = i + 1; j < nums.length; j++) {preSum += nums[j - 1];double avg = dp[j][p - 1];if (avg != -1 && preSum / (j - i) + avg > result) result = preSum / (j - i) + avg;}if (result != -1) dp[i][p] = result;}}return dp[0][k];}// 當前位置是i，后面還有p段可以分的時候，返回最大的avg之和。 // public double process(int[] nums, int i, int p, double[][] dp) { // if (dp[i][p] != Integer.MIN_VALUE) return dp[i][p]; // // if (p == 1) { // double sum = 0; // for (int j = i; j < nums.length; j++) { // sum += nums[j]; // } // dp[i][p] = sum / (nums.length - i); // return dp[i][p]; // } // // double result = -1; // double preSum = 0; // for (int j = i + 1; j < nums.length; j++) { // preSum += nums[j - 1]; // double avg = process(nums, j, p - 1, dp); // if (avg != -1 && preSum / (j - i) + avg > result) result = preSum / (j - i) + avg; // } // dp[i][p] = result; // return dp[i][p]; // } }

總結

以上是生活随笔為你收集整理的leetcode 813. Largest Sum of Averages | 813. 最大平均值和的分组（暴力递归-＞傻缓存-＞DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。