java class 反射 软件开发 dictionary animation iframe installation ros 打印 vue引入组件 网赚教程下载 直销系统源码 oracle查询所有数据库 bootstrap时间轴 oracle查看数据库状态 arduino程序 ipex接口 matlab注释一段 python网络编程 java实例 java注释 java运算符 java中的注释 java中string的方法 java方法调用 java抛出自定义异常 java语言入门 java网页 java字符比较 linuxsudo命令 嵌入式开发教程 网络电视软件下载 win10计算器下载 vnc客户端 fireworks8 sim卡注册失败 工信部手机入网查询 python爬虫代码 mysql导出数据 脚本网站 js给标签添加属性
当前位置: 首页 > 学习教程  > python

【leetcode】813. Largest Sum of Averages

2021/2/6 22:25:10 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目描述: https://leetcode.com/problems/largest-sum-of-averages/submissions/ 题目大意: 讲一个整数数组分成连续的K个子数组,问这K个子数组的平均值之和的最大值是多少? 解决思路: 就相当于在len(A)长度的数组…

题目描述:

https://leetcode.com/problems/largest-sum-of-averages/submissions/

题目大意:

讲一个整数数组分成连续的K个子数组,问这K个子数组的平均值之和的最大值是多少?

解决思路:

就相当于在len(A)长度的数组中存在的len(A)-1个间隔中插入K-1个“隔板”使得分隔开来的K个连续子数组平均值之和最大。

可以使用回溯进行遍历。这里注意到当前几个隔板放置好后,余下的数组长度和隔板数量对应的子问题答案是会在回溯过程中被反复求解的,也就是出现了重复子问题,可以使用动态规划,即记忆化回溯。使用一个memory字典记录(长度,隔板数目)对应的子问题的解

另一个思路是直接使用dp矩阵进行求解。思路类似矩阵相乘次数最少那道题目(后续补充)

python 记忆化回溯代码:

class Solution(object):
    def largestSumOfAverages(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: float
        """
        memory = {}
        res = [0]
        self.helper(A,K,memory,0,res)
        print(memory)
        return res[0]
        
    def helper(self,A,K,memory,now_sum,res):
        if K>len(A):
            return 0
        elif K==len(A):
            res[0] = max(res[0],now_sum + sum(A))
            return sum(A)
        elif K<len(A) and K==1:
            res[0] = max(res[0],now_sum + float(sum(A))/len(A))
            return float(sum(A))/len(A)
        else:
            if (len(A),K) in memory:
                res[0] = max(res[0],now_sum + memory[(len(A),K)])
            else:
                memory[(len(A),K)] = -1
                for i in range(0,len(A)-1):
                    memory[(len(A),K)] = max(memory[(len(A),K)],float(sum(A[:i+1]))/(i+1)+self.helper(A[i+1:],K-1,memory,now_sum + float(sum(A[:i+1]))/(i+1),res))
                res[0] = max(res[0],now_sum + memory[(len(A),K)])
            return memory[(len(A),K)]

二维dp矩阵python代码:

class Solution(object):
    def largestSumOfAverages(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: float
        """
        def dp(A, K):
            dp = [[0] * len(A) for _ in range(K)]
            for j in range(len(A)):
                dp[0][j] = self.mean(A[:j + 1])
            for k in range(1, K):
                for j in range(k, len(A)):
                    for i in range(j):
                        dp[k][j] = max(dp[k][j], dp[k - 1][i] + self.mean(A[i + 1:j + 1]))
            return dp[-1][-1]
        return dp(A, K)
    
    def mean(self,L):
        return float(sum(L))/len(L)

 


本文链接: http://www.dtmao.cc/news_show_2000081.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?