python分段求均值_813. 最大*均值和的分组(Python)

发布时间:2021-12-03 11:59:43

难度:★★★☆☆


类型:数组


方法:动态规划


力扣链接请移步本题传送门


更多力扣中等题的解决方案请移步力扣中等题目录


题目


我们将给定的数组 A 分成 K 个相邻的非空子数组 ,我们的分数由每个子数组内的*均值的总和构成。计算我们所能得到的最大分数是多少。


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


示例:


输入:


A = [9,1,2,3,9]


K = 3


输出: 20


解释:


A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.


我们也可以把 A 分成[9, 1], [2], [3, 9].


这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.


说明:


1 <= A.length <= 100.


1 <= A[i] <= 10000.


1 <= K <= A.length.


答案误差在 10^-6 内被视为是正确的。


解答


数组问题常用动态规划来解决。动态规划的精髓在于,把一个难以解决的大问题转化为若干个可以通过有限次重复解决的简单问题。接下来从动态规划的几个要素进行介绍:


【数组定义】


我们定义一个二维数组dp,维度为输入数组A的维度×K,dp[i][k]表示数组A[:i+1]被分成k+1组时,可以得到的最大分数(各组*均值的和)。这里尤其需要注意python下标和它代表的变量的物理含义之间正好相差1的。


【初始状态】


我们可以很快得知的信息是,如果数组只被分为一组的情况。因此可以先把k=0的一列填好。这一列各个位置dp[i][0]的填充规则,就是A[:i]的均值。


【递推公式】


我们以分组数k和下标i递增的方式,构造嵌套循环。这里还需要留意一个情况,就是填充dp[i][k]时,需要考虑到获得当前位置的各种情况的分组,因此借助一个中间下标变量j,范围从0到i,也就是说,我们把数组A[:i+1]从下标j砍成了两半,因此当前位置处的值可以填充为:


dp[i][k] = max(dp[i][k], dp[j][k-1]+average(j+1, i+1))


这里average是一个函数,用来计算A[i:j]子数组的均值。这里把i和j+1的原因是我们定义dp数组的物理意义决定的。


有了这个递推公式,就可以迭代进行计算了,


注意k的范围是从1到K,因为k=0的一列已经算好了;


i的范围是从k到len(A),因为组的个数不能比数组中数字的个数还要多;


j的范围是小于i,因为必须要保证可以把A[:i+1]分开。


【最后结果】


最终范围dp[-1][-1]也就是最后计算出的值,就可以代表题目所要求的结果。


class Solution(object):


def largestSumOfAverages(self, A, K):


P = [0]


for x in A:


P.append(P[-1] + x)


print(P)


def average(i, j):


return (P[j] - P[i]) / float(j - i)


N = len(A)


dp = [[0 for _ in range(K)] for _ in range(len(A))]


for i in range(len(A)):


dp[i][0] = average(0, i+1)


for k in range(1, K):


for i in range(k, N):


for j in range(i):


dp[i][k] = max(dp[i][k], dp[j][k-1]+average(j+1, i+1))


print("数组[{}]被分成{}份,*均值的和为{}".format(",".join(map(str, A[:i])), k+1, dp[i][k]))


print(dp)


return dp[-1][-1]


如有疑问或建议,欢迎评论区留言~


有关更多力扣中等题的python解决方案,请移步力扣中等题解析

相关文档

  • Codeforces Round #343 (Div. 2) D. Babaei and Birthday Cake(线段树+离散化优化DP)
  • yota3墨水屏设置_高刷墨水屏的海信 A5 Pro 体验报告
  • 会争吵的玩具
  • 汽车行业的求职信
  • 粉色墙面壁纸装修效果图
  • 台式电脑的硬件组成部分及其作用各是什么
  • 智能机的外屏和内屏是什么外屏是触摸屏内屏是显示屏
  • 日本福而可马油面霜效果怎么样?宝宝用滋润吗?
  • 驾照证科目一考试技巧
  • 小篮球小知识
  • 三峡精品教学反思
  • 企业绿色环保口号
  • 医院团支部年度工作计划
  • React受控组件与非受控组件
  • 怎么把群记录删掉
  • 没房想结婚怎么办理
  • 斯诺登在莫斯科做宅男 自称已经取得胜利
  • iot nb 曹淑敏 鹰潭_5分钟理解NB-IOT应用场景 | NB-IOT系列2/4
  • java获取两个时间的间隔天数_java获取两日期的间隔天数
  • 高一班主任工作总结5篇精选
  • 转发性通告范文
  • 星级酒店开业典礼领导讲话稿
  • Python基础????25、Python OS文件/目录方法
  • 一文详解synchronized与volatile
  • 中国第一宰相管仲
  • 自己建房基本常识
  • 贝透是什么
  • 宜家创始人坎普拉德的创业三部曲
  • 北京人是如何“出世”的?
  • 分清楚if else的三种结构
  • 猜你喜欢

  • 秀山土家族苗族自治县人民政府办公室关于进一步做好城乡居民最低
  • 2018-2019学年高中政治必修一课时规范训练:7.1按劳分配为主 多种分配方式并存 Word版含解析
  • 人们愿意为精品等待_励志故事
  • 医院外科医生辞职报告精选模板
  • 日常计算机维修心得(硬盘)篇
  • 仓储型物流企业绩效评价研究
  • 加强基层农机监理工作的具体措施与建议
  • 道真自治县腾星电力发展有限责任公司(企业信用报告)- 天眼查
  • 辉瑞制药2013校园招聘大礼包_笔试面试经验汇总@大街网@应届生校园招聘 制作
  • 一年级(下)看拼音写汉字(第五单元)
  • 二维码技术在舰船消磁装备信息管理中的应用
  • 小学数学总复*学*资源设计策略及教学模式研究
  • 全英面试攻略,面试英文自我介绍,英文面试常见问题,英文面试对话
  • 如何通过班组自主管理加强班组安全建设
  • 最新西师大版语文五年级上册《心田上的百合花》优秀学案(精品)
  • 使用IDA Pro调试Android原生程序(远程运行)
  • 医学-*回收技术的临床应用
  • 高考物理一轮复* 第三章 牛顿运动定律单元过关检测(4)
  • 浅谈阿勒泰地区非物质文化遗产的保护与传承
  • 2015高中毕业生登记表自我鉴定大全
  • winrar 篇
  • 全国农机化示范区建设成交显著
  • 功能清热凉血,养阴生津的药物是() A.生地黄 B.玄参 C.牡丹皮
  • 最新-党员思想汇报2019年 大学生思想汇报2019年3月,党的基本知识 精品
  • 香缇别苑(玫瑰香橙)
  • 眼睛、鼻子、与嘴的争论。
  • 人教版初中物理八年级上册第一章第1节 长度和时间的测量 课件(共17张PPT)
  • 小学五年级日记:春天的校园
  • 初一入团志愿书格式300字
  • 员工行为分析及激励方法(ppt 41页)
  • 绥中县塔山镇高氏推拿理疗馆企业信息报告-天眼查
  • Go语言的历史档案 | Gopher Daily (2020.09.16)
  • 教育实*报告总结2000字 实*报告总结3000字
  • 属蛇人的婚姻与爱情分析
  • ASP.NET MVC自学总结
  • 【车辆租赁合同范本】车辆无偿租赁协议范本
  • 最新高一英语阅读理解(时文广告)的基本方法技巧及练*题及练*题(含答案)
  • 我过了一个快乐的年
  • 初二写人作文:谢谢你,为我助跑
  • 微课在高中生物教学中应用的教学模式
  • 如何提高影楼团队凝聚力
  • 情侣配套个性签名
  • 电脑版