本文最后更新于:2023年2月25日 晚上
题目描述

思路及实现
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]
。
最后写出状态转移方程:

1 2 3 4 5 6 7 8 9 10 11 12 13
| 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)] for index in range(1, len(nums) + 1): dp[index][1] = prefix[index] / index for j in range(2, k + 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]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| 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)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| 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; } }
|
垃圾话
怎么有人欠题目欠了三个月的啊?就en⬆摆是吧?
私密马赛红豆泥私密马赛(90°鞠躬*n

希望本文章能够帮到您~