Leetcode - 312 Burst Balloons_312. burst balloons-程序员宅基地

技术标签: leetcode  OJ  dp  

Leetcode - 312 Burst Balloons

解题思路

动态规划
  • 为了方便,做如下处理
    • nums = [1] + nums + [1]
    • dp = [[0] * len(nums) for i in range(len(nums)) ]
  • 动态方案
    • dp[i][j]表示从nums[i:j+1]的最佳方案,注意这里的最佳是在指定nums[i-1]nums[j+1]为临下的最佳
    • 递推关系dp[i][j] = max(dp[i][k-1] + dp[k+1][j] + nums[i-1] * nums[k] * nums[j+1]) [ i <= k <= j ]
    • dp[1][len(nums)-2]为最终结果

AC源码

Code (Python2)
class Solution(object):
    def maxCoins(self, nums):
        nums = [1] + nums + [1]
        l = len(nums)
        dp = [[0] * l for i in range(l)]
        for i in reversed(range(1, l-1)):
            for j in range(i, l-1):
                for k in range(i, j+1):
                    dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + nums[k] * nums[i-1] * nums[j+1])
        return dp[1][l-2]
Comment
[
    [0, 0, 0, 0, 0, 0], 
    [0, 3, 30, 159, 167, 0], 
    [0, 0, 15, 135, 159, 0], 
    [0, 0, 0, 40, 48, 0], 
    [0, 0, 0, 0, 40, 0], 
    [0, 0, 0, 0, 0, 0]
]
  • 动态规划,数组的遍历顺序很重要。i是反向遍历,j是顺序遍历,右上角为最终答案
  • 遍历下标是从[1,l-1],不是从0开始,也不是l结束

    2

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ZhengJingWuLai/article/details/78552882

智能推荐

人生还需要正能量_气我去者昨日之日不可留乱我心者今日之日多烦忧什么意思-程序员宅基地

文章浏览阅读492次。弃我去者,昨日之日不可留;乱我心者,今日之日多烦忧。无论是时光,还是往事,或是容颜,都如昨日之日一般弃我而去,任我多么留恋,它们却毫无回头之意。而今日之日又有诸多烦忧纷纷扰扰,挥之不去。人生就是有这样的错觉:逝去的总是美好的,拥有的总是缺憾的,于是,在眺望昨日的背影时,眼里只有烦恼的身影来来回回。_气我去者昨日之日不可留乱我心者今日之日多烦忧什么意思

出现java.lang.NoClassDefFoundError: org/apache/commons/collections/FastHashMap错误问题解决-程序员宅基地

文章浏览阅读1.4k次,点赞2次,收藏2次。首先出现这个问题,你应该是用了BeanUtils.populate(meter,map);import org.apache.commons.beanutils.BeanUtils;并且导入了commons-beanutils-1.9.2.jar , commons-logging-1.2.jar这俩包如果是那么我可能就能解决你的问题。java.lang.NoClassDefFo..._java.lang.noclassdeffounderror: org/apache/commons/collections/fasthashmap

PyQt(Python+Qt)学习随笔:使用QtWidgets.qApp实现在程序中随时访问应用的方法_qtwidgets.qapplication-程序员宅基地

文章浏览阅读1.6k次。在PyQt应用中,任何一个应用在启动时必须创建一个基于QtWidgets.QApplication或其派生类对应的应用对象,该对象用于处理事件。如果需要在应用代码中的任何位置都能访问该应用对象,可以通过“QtWidgets.qApp”访问应用及其属性。示例代码1: QtWidgets.qApp.popwin = self.createPopwin(winTypeChoice) QtWidg..._qtwidgets.qapplication

微专业 Python精进路线展望 第一周_对于一个已有函数如何更新其功能?(同名使用)-程序员宅基地

文章浏览阅读166次。上下文Context:程序执行中某个状态程序执行所需的一些内外部参数,构成了程序运行时的状态。上下文是用来表达程序运行状态的概念,对应内存状态。上下文是程序中断保留或恢复运行的重要状态信息。上下文管理器:一个可以在程序中加载独立上下文的对象万物皆对象:上下文管理器也是一个对象,管理者一个独立上下文区域。上下文管理器使用with显示创建。进入和退出分别对应__enter__()和..._对于一个已有函数如何更新其功能?(同名使用)

mysql 41000_mysql-SQL Error: 1205, SQLState: 41000-程序员宅基地

文章浏览阅读251次。mysql-SQL Error: 1205, SQLState: 41000——CSDN问答频道https://ask.csdn.net/questions/176492mysql-SQL Error: 1205, SQLState: 41000-mysql教程-PHP中文网http://www.php.cn/mysql-tutorials-82336.htmlJDBC exception on ..._jdbc exception on hibernate data access: sqlexception for sql code [1205]

Java、Javascript、Javaweb三者的区别-程序员宅基地

文章浏览阅读5.4w次,点赞61次,收藏170次。首先,我们来说一下java 与 javaweb之间的关系 : 我们平常说的Java一般指Java SE,也就是Java Standard Edition,Java的标准版,一般用来开发桌面应用程序,但是在开发桌面应用程序上相对VB,Delphi,VC++并没有什么优势。 JavaWeb则到了Java EE领域了,也就是Java Enterprise Edition,Java的企业版,看那

随便推点

关于非全日制找实习_非全研究生在别的公司实习-程序员宅基地

文章浏览阅读1.6k次。https://www.zhihu.com/question/68031329?sort=created_非全研究生在别的公司实习

MTK 平台使用mtklogger 抓取日志-程序员宅基地

文章浏览阅读4.2k次。使用mtk工具 抓取系统日志_mtklogger

lInux安装jdk的三种方法_linux 安装jdk-13.0.1-程序员宅基地

文章浏览阅读271次。环境Linux版本:CentOS 6.5、Ubuntu 12.04.5JDK版本:JDK 1.7方法一:手动解压JDK的压缩包,然后设置环境变量方法二:用yum安装JDK方法三:用rpm安装JDK方法四:Ubuntu 上使用apt-get安装JDK方法一:手动解压JDK的压缩包,然后设置环境变量1.在/usr/目录下创建java目录..._linux 安装jdk-13.0.1

SQL SERVER学习(五)——CentOS7下安装SQL SERVER_1.1、通过yum,下载sql server的源;-程序员宅基地

文章浏览阅读3.2k次,点赞4次,收藏12次。官方文档:https://docs.microsoft.com/en-us/sql/linux/quickstart-install-connect-red-hatOS必须条件: Memory: 3.25 GBFile System: XFS or EXT4 (other file systems, such as BTRFS, are unsupported)Disk sp..._1.1、通过yum,下载sql server的源;

SpringSecurity学习(Springboot+SpringSecurity+Jwt)_spring boot + spring security + jwt-程序员宅基地

文章浏览阅读478次。一、简介1、什么是SpringSecuritySpringSecurity是Spring家族的一个安全性框架。相比与Shiro,它提供了更多的功能。一般来说中大型项目都使用SpringSecurity作为安全框架。小项目用Shiro比较多,因为Shiro相对于SpringSecurity更加容易上手。一般Web应用需要认证和授权。认证:验证访问系统的是不是本系统的用户,而且要确认具体是哪个用户。授权:经过认证后,如果该用户想访问该系统资源,要判断是否有权限访问。2、如何引入Spring_spring boot + spring security + jwt

Dialer_InCallUi启动流程and数据更新流程_incallui ondetailschange-程序员宅基地

文章浏览阅读929次,点赞4次,收藏6次。1, InCallActivity界面信息的显示2, NotificationBroadcastReceiver这个类是广播接收器,一般没有用到。主要作用是第三方app可以发送广播的方式进行通话的相关操作,例如,挂断/接听等等。接收广播后,都是调用InCallPresenter的相关方法完成的,部分代码如下,InCallPresenter.getInsta..._incallui ondetailschange