leetcode 813. Largest Sum of Averages | 813. 最大平均值和的分组（暴力递归-＞傻缓存-＞DP）

题目

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: 自底向上的dp
        for (int i = nums.length; i >= 0; i--) { // from index i
            for (int p = 1; p <= k; p++) { // p partition
                if (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];
//    }
}