力扣-813. 最大平均值和的分组

本文最后更新于：2023年2月25日晚上

题目描述

813

思路及实现

dp问题，啊，一定要好好从入门做起，啊，不要上来就看这种看半天都没点想法，啊，对水平提升很没帮助，啊，就是我，啊(悲
不过好在起码是能看懂别人的思路的(
这边学到了两种思路，一种是前缀和+深度优先搜索，另一种是前缀和+动态规划。

前缀和+动态规划

思路参考：官解
因为本题需要用到平均值，为了方便计算，可以用一个数组prefix先把前缀和保存起来。
然后思考动态规划用到的数组dp[i][j]如何设计，以及写出转移方程。要找出给定数组的最大分数，我们可以先找更小数组中的最大分数，那就让i表示前nums中的前i个（不包括i）元素，j表示切分的子数组数，那么dp[i][j]的意思就是nums使用前i个（不包括第i个）元素并切分成j个子数组的最大平均值和。
接着找出一般情况和特殊情况，根据这些情况就能够写出转移方程了：

特殊情况：当j = 1时，dp[i][j]的值就是前i个元素的平均值。

一般情况：当j > 1时，就利用枚举，从第x = j - 1个元素开始（因为最小分组不能为空，至少需要一个元素）到i - 1，将dp[i][j]分为两个部分，[0, x - 1]和[x, i - 1]，比较当前dp[i][j]和dp[x][j - 1] + (prefix[i] - prefix[x]) / (i- x)的值哪个更大，用大的值更新dp[i][j]。
最后写出状态转移方程：
813_dp

class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        prefix = [0]
        for index, num in enumerate(nums):
            prefix.append(prefix[index] + num)  # 计算前缀和
        dp = [[0.0] * (k + 1) for _ in range(len(nums) + 1)]  # 初始化dp数组
        for index in range(1, len(nums) + 1):  # 处理j = 1的情况
            dp[index][1] = prefix[index] / index
        for j in range(2, k + 1):  # 处理j > 1的情况
            for i in range(j, len(nums) + 1):
                for x in range(j - 1, i):
                    dp[i][j] = max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x))
        return dp[len(nums)][k]

public class Solution {
    public double LargestSumOfAverages(int[] nums, int k)
        {
            int n = nums.Length;
            double[] prefix = new double[n + 1];
            for (int i = 0; i < n; i++)
            {
                prefix[i + 1] = prefix[i] + nums[i];
            }
            double[][] dp = new double[n + 1][];
            for (int i = 0; i <= n; i++)
            {
                dp[i] = new double[k + 1];
            }
            for (int i = 1; i <= n; i++)
            {
                dp[i][1] = prefix[i] / i;
            }
            for (int j = 2; j <= k; j++)
            {
                for (int i = j; i <= n; i++)
                {
                    for (int x = j - 1; x < i; x++)
                    {
                        dp[i][j] = Math.Max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));
                    }
                }
            }
            return dp[n][k];
        }
}

前缀和+深度优先搜索

思路参考：ylb

class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        @cache
        def dfs(i, k):
            if i == n:
                return 0;
            if k == 1:
                return (s[-1] - s[i]) / (n - i)
            ans = 0
            for j in range(i, n):
                t = (s[j + 1] - s[i]) / (j - i + 1) + dfs(j + 1, k + 1)
                ans = max(ans, t)
            return ans

        n = len(nums)
        s = list(accumulate(nums, initial = 0))
        return dfs(0, k)

public class Solution {
    private double[,] f;
    private int[] s;
    private int n;

    public double LargestSumOfAverages(int[] nums, int k)
        {
            n = nums.Length;
            s = new int[n + 1];
            f = new double[n + 1, k + 1];
            for (int i = 0; i < n; i++)
            {
                s[i + 1] = s[i] + nums[i];
            }
            return dfs(0, k);
        }

        private double dfs(int i, int k)
        {
            if (i == n)
            {
                return 0;
            }
            if (k == 1)
            {
                return (s[n] - s[i]) * 1.0 / (n - i);
            }
            if (f[i, k] != 0)
            {
                return f[i, k];
            }
            double ans = 0;
            for (int j = i; j < n; ++j)
            {
                double t = (s[j + 1] - s[i]) * 1.0 / (j - i + 1) + dfs(j + 1, k - 1);
                ans = Math.Max(ans, t);
            }
            return f[i, k] = ans;
        }
}