区间dp笔记√

区间dp笔记√

区间DP是一类在区间上进行dp的最优问题,一般是根据问题设出一个表示状态的dp,可以是二维的也可以是三维的,一般情况下为二维。

然后将问题划分成两个子问题,也就是一段区间分成左右两个区间,然后将左右两个区间合并到整个区间,或者说局部最优解合并为全局最优解,然后得解。


 区间dp就是f[i][j]表示i到j的一段区间, 然后去转移最优值的dp

一段区间表示一段状态,维护i~j的最优值来转移。

常见区间dp有:合并石子,破环成链类题目

 


 其实对于环形区间DP有一个对付环的好方法:关于N取模(特殊处理0)!

e.g.能量项链

设 f[i,j]为第i到j颗珠子合并的最大能量为max{f[i,k]+f[k+1,j]+a[i]*a[k+1]+a[j+1]};//对k+1,j,j+1等数字关于m取模

这样一来,i>j时 合并就是从i到n在回到1再到j
若使用复制一次数组的方法,时间复杂度为(2*n)^3,空间复杂度为4*n^2
环形取模方法与链式区间空间复杂度相同,且无空间浪费,时间复杂度为n^3


 求和(e.g.石子合并)

对于求和的区间DP最重要的前缀和优化( 要不然就要多花时间在求和上面 ) 这种问题我们先考虑其中最大的区间1—2*n (因为是绕成一圈所以是2*n,2*n的话可以保证在一个环上所有的区间情况)。

那么对于最大的区间1—2*n, 首先我们可以知道如果他们只有两个的话那么是可以直接合并的, 而且还有一个条件可以确定,就是当区间中只有一个元素的时候,答案是0

那么对于一个我们不知道答案的区间,计算他的答案有两个方面

①要求区间和

②要找到一种方法把自己分成两个区间

分成两个区间的时候,我们需要知道当前分成这两个区间之后的最大答案是多少。那么我们就枚举再哪里切断这个大区间让他变成两个小区间

于是就推得了状态转移方程。 
 
 

 

转载于:https://www.cnblogs.com/gc812/p/5777201.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108904.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Java String.replace()方法

    Java String.replace()方法用法实例教程,返回一个新的字符串,用newChar替换此字符串中出现的所有oldChar声明以下是java.lang.String.replace()方法的声明public String replace(char oldChar, char newChar)参数oldChar — 这是旧的字符.newChar — 这是新

  • navicate 15 免费激活码(JetBrains全家桶)

    (navicate 15 免费激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • 手动更新PIP(手机怎么手动更新)

    有时候使用命令行无法更新PIP,此时需要手动进行更新。可以参考:https://blog.csdn.net/lyj_viviani/article/details/70568434

  • 拉链表的实现过程[通俗易懂]

    拉链表的实现过程[通俗易懂]拉链表的优势我就不说了,具体请参考百度百科:拉链表-百度百科推荐一个比较详细的参考文章:拉链表示例主要总结一下实现过程:分析:拉链表就是用来存储变化的数据的,每一份数据都有对应的有效期,我们需要进行的操作就是将变动的数据进行新增,同时将变动对应的前一条数据的有效期进行变更。说明:一般都是今天处理昨天的数据,本文所说的当天为所处理的数据的产生的当天。在这之前需要熟悉一下需要用到的表:表1:订单表(记录原始的数据)表2:增量数据表(记录每日变更的数据)表3:历史拉链表(我们要得到的就是这张表

  • C语言 — void的用法解析[通俗易懂]

    C语言 — void的用法解析[通俗易懂]C语言-void的用法解析简介​ void中文翻译为”无类型”,有的也叫”空类型”。常用在程序中对定义函数的参数类型、返回值、函数中指针类型进行声明。用法​ void应用最广泛的就是跟指针结合,即void* //无类型指针,也称为空指针,可以指向任何类型的数据 //注意一点:当我们需要使用void类型的的指针变量区指向 某一类型的变量的时候,必须要对其进行类型转换​ 这里补充一点:因为我们在定义一个指针变量的时候第一件事就是指定我们指针变量所指向的变量的类型。一

  • 【边缘计算】边缘计算元年一文看懂云边协同!九大场景带来新一轮信息革命…

    【边缘计算】边缘计算元年一文看懂云边协同!九大场景带来新一轮信息革命…来源:产业智能官2019年边缘计算备受产业关注,一度引起了资本市场的投资热潮,很多人把2019年称作边缘计算的元年。理性来看,造成如此火爆局势难免有一些炒作因素在推…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号