【每日一题Day41】LC813最大平均值的和分组 | 序列DP
admin
2024-02-24 07:21:12
0次

最大平均值的和分组【LC813】

You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in nums, and that the score is not necessarily an integer.

Return the maximum score you can achieve of all the possible partitions. Answers within 10-6 of the actual answer will be accepted.

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。

注意我们必须使用 nums 数组中的每一个数进行分组,并且分数不一定需要是整数。

返回我们所能得到的最大 分数 是多少。答案误差在 10-6 内被视为是正确的。

隔离第4天…
学习使我忘记时间…

序列dp

  • 思路:将 n 个元素划分为k个连续子数组,最大化子数组的平均值之和。
  1. 确定dp数组(dp table)以及下标的含义

    dp[i][j]:将长度为[0,i]的nums分割为j个连续子数组时,得到的最大分数

  2. 确定递推公式

    当j≤kj\le kj≤k时,nums[i]有两种选择,自成一组,或者并入前一组

    • 自成一组:dp[i][j]=dp[i−1][j−1]+num[i]dp[i][j] = dp[i-1][j-1] + num[i]dp[i][j]=dp[i−1][j−1]+num[i]

    • 并入前一组:对于每个nums[i],需要枚举前一组所有可能的初始位置,为了方便计算平均值,使用preSum数组计算前缀和,由于每个子数组至少包含一个元素,因此start∈[1,i)start\in[1,i)start∈[1,i)

      dp[i][j]=dp[start−1][j−1]+ave(nums[start,i])dp[i][j]=dp[start-1][j-1] + ave(nums[start,i])dp[i][j]=dp[start−1][j−1]+ave(nums[start,i])

    • 以上两个公式可合并为一个:当start=istart=istart=i时,新的一组只有nums[i]nums[i]nums[i]一个元素
      dp[i][j]=max(dp[i][j],dp[start−1][j−1]+ave(nums[start,i]))dp[i][j] = max(dp[i][j],dp[start-1][j-1]+ave(nums[start,i])) dp[i][j]=max(dp[i][j],dp[start−1][j−1]+ave(nums[start,i]))

      start∈[1,i]start\in[1,i] start∈[1,i]

    • preSum[i]preSum[i]preSum[i]为前i−1i-1i−1个数组元素之和,因此连续子数组nums[start,i]nums[start,i]nums[start,i]的平均值可表示为
      ave=(preSum[i+1]−preSum[start−1])/(i−start+1)ave=(preSum[i+1] - preSum[start-1])/(i-start+1) ave=(preSum[i+1]−preSum[start−1])/(i−start+1)

  3. dp数组如何初始化

    特殊处理只分为一组时的dp[i][1]

    • dp[0][1]=nums[0]dp[0][1] = nums[0]dp[0][1]=nums[0]
    • dp[1][1]=(nums[0]+nums[1])/2dp[1][1] = (nums[0] + nums[1])/2dp[1][1]=(nums[0]+nums[1])/2
    • dp[i][1]=(nums[0]+nums[1]+……+nums[i])/(i+1)=preSum[i+1]/(i+1)dp[i][1] = (nums[0] + nums[1] + ……+nums[i])/(i+1) = preSum[i+1]/(i+1)dp[i][1]=(nums[0]+nums[1]+……+nums[i])/(i+1)=preSum[i+1]/(i+1)
  4. 确定遍历顺序

    由dp公式可知,外层正序遍历i,内层正序遍历子数组个数j,最后遍历第j个子数组的可能的起始位置start

  5. 举例推导dp数组

  • 代码 :

    • 下标均从1开始遍历,代码较清晰
      • dp[i+1][j]:将长度为[0,i]的nums分割为j个连续子数组时,得到的最大分数
      • preSum[i+1]对应前i个nums
    • 只有数组元素大于等于j时才有可能划分为j个连续子数组
    class Solution {public double largestSumOfAverages(int[] nums, int k) {int len = nums.length;double[][] dp = new double[len + 1][k + 1];double[] preSum = new double[len + 1];for (int i = 1; i <= len; i++){preSum[i] = preSum[i-1] + nums[i-1];}for (int i = 1; i <= len; i++){dp[i][1] = preSum[i] / i;}for (int i = 1; i <= len; i++){for (int j = 2; j <= k && j <= i; j++){// 自成一组 与start = i 合并// dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + nums[i-1]);// 并入前一组nums[start,i]for (int start = 2; start <= i; start++){double ave = (preSum[i] - preSum[start - 1]) / (i - start + 1);dp[i][j] = Math.max(dp[i][j],dp[start - 1][j - 1] + ave);}}}return dp[len][k];}
    }
    
    • 复杂度

      • 时间复杂度:O(n2∗k)O(n^2*k)O(n2∗k)
      • 空间复杂度:O(n∗k)O(n*k)O(n∗k)
  • 代码:很丑

    dp[i][j]:将长度为[0,i]的nums分割为j个连续子数组时,得到的最大分数

    class Solution {public double largestSumOfAverages(int[] nums, int k) {int len = nums.length;double[][] dp = new double[len][k + 1];double[] preSum = new double[len + 1];for (int i = 0; i < len; i++){preSum[i+1] = preSum[i] + nums[i];}for (int i = 0; i < len; i++){dp[i][1] = preSum[i + 1] / (i+1);}for (int i = 0; i < len; i++){for (int j = 2; j <= k && j <= i + 1; j++){// 自成一组 与start = i 合并// dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1] + nums[i-1]);// 并入前一组nums[start,i]for (int start = 1; start <= i; start++){double ave = (preSum[i + 1] - preSum[start]) / (i - start + 1);dp[i][j] = Math.max(dp[i][j],dp[start - 1][j - 1] + ave);}}}return dp[len - 1][k];}
    }
    

相关内容

热门资讯

智星菠萝德州辅助神器!如何下载... 智星菠萝德州辅助神器!如何下载德普之星辅助软件”原来真的是有辅助操作1)如何下载德普之星辅助软件辅助...
WPK辅助插件!aapoker... WPK辅助插件!aapoker怎么控制牌”原来有辅助项目1、起透看视 aapoker怎么控制牌辅助软...
红龙PoKer开挂工具!德扑圈... 红龙PoKer开挂工具!德扑圈透视”确实真的是有开挂方针1、该软件可以轻松地帮助玩家将德扑圈透视辅助...
WPK透视挂攻略!扑克之星辅助... WPK透视挂攻略!扑克之星辅助”果然真的是有透视挂法子1、游戏颠覆性的策略玩法,独创攻略技巧玩法,可...
红龙PoKer开挂教程!wpk... 红龙PoKer开挂教程!wpk系统是否存在作弊行为”一贯是有开挂办法1、完成wpk系统是否存在作弊行...
AApoker透视挂脚本!红龙... AApoker透视挂脚本!红龙poker辅助器免费观看”竟然存在有透视挂演示1、AApoker透视挂...
wpk开挂插件!aapoker... wpk开挂插件!aapoker怎么选牌”本来有开挂模块1、用户打开应用后不用登录就可以直接使用,点击...
微扑克透视技巧!智星菠萝辅助”... 微扑克透视技巧!智星菠萝辅助”本来是有透视学习1、操作简单,无需智星菠萝辅助手机版透视脚本,只需要使...
wpk辅助器app!aapok... wpk辅助器app!aapoker怎么开辅助器”都是真的是有辅助器策略1、下载好aapoker怎么开...
德扑之星透视工具!wpk透视是... 德扑之星透视工具!wpk透视是真的假的”本来真的有透视妙招一、wpk透视是真的假的游戏安装教程牌型概...