精华内容
下载资源
问答
  • 各位同学上一节课我们讲解了一个多分类的问题,让我们从现在开始会讲一些在深度学习中间时候的一些小技巧这些小技巧可是帮助大家理解深度学习一个非常必要的环节,首先我们来看第一个深度学习中存在的一个问题就是过...

    课前小例子

    各位同学上一节课我们讲解了一个多分类的问题,让我们从现在开始会讲一些在深度学习中间时候的一些小技巧这些小技巧可是帮助大家理解深度学习一个非常必要的环节,首先我们来看第一个深度学习中存在的一个问题就是过拟合和和欠拟合。
    在这里插入图片描述

    在讲解过拟合和和欠拟合之前,我们来讲一个数据的真实的模态,

    我们把它一个叫做数据的真实分布

    那么我们来看第一个例子就是房价例子,然后房价的这个x坐标表示它的房子的面积,因此这里的面积就是area的意思,平方的面积,然后这边的y表示价格,我们可以很好的知道房子的面积和价格是一个这样的线型的模型,它就是面积越大,然后房价越高,它这个模型她为什么是线性的模型呢?因为我们的房价定义的时候就是这么定义的,我们就是一个面积乘一个倍数,然后可能再加上一个偏置,会得到一个房价的一个生产的一个房价的一个价格,这是一个非常简单的线性模型,我们不管是根据这个,不管是根据我们人的经验来说,还是根据这个数据的分布来说,我们都能够一眼的就推测出来,房价跟面积就是一个非常简单的线性模型,

    那我们再来看一个非线性的模型,
    在这里插入图片描述

    就比如说我们一个班级的一个GPA,然后他 的x坐标就是你的GPA,我们这里就忽略一下具体数字,就比如说是三年级啊,四点几的样子,然后他的y坐标就是对应的,GPA,对应的一个人数吧,我们可以看到基本上在GPA中间,比如说在三左右指人数是比较高的,然后3到4。3.5以上就是比较优秀的学生,学霸啊,这个区域就是学霸这个区域的话,学生比较少。对于学渣来说也比较少,大部分的人都是普通人,他们成绩可能就在这个区间里面,这也是我们老师给分的时候,一个原则就是给分的时候,尽可能的让你中间的分数让70分到80分的时候稍微多这样子的话根据他们的这种先验 ,她们生成这个分数也会符合这个分布,我们一般来讲,是把它近似于一个高斯分布。所以的话,我们可以把学生的一个班上的或一个学校里面的GPA一个成绩的G点的分布,理解为一个高斯分布。

    对于我们之前提到两种情况,要么就是我们能够很清楚地知道它一定是属于线性分布

    ,就比如说那个房价和面积,或者是根据我们的这种经验来说,发现她的成绩和学生的数量基本上是属于一个这样的高斯分布,这两种情况,我们。在某种场合都可以说,我们已经提前知道了这个数据的分布,只是我们不知道这个模型的具体参数就比如说你这个房价倍率,这比如说你这个房价的倍率是多少,然后你这个学生的高斯分布的均值在哪里?到底是70分还是80分呢?还是85分呢?或者说你考试的难度不一样啦,会造成这个均值和方差的改变,对吗?

    在我们已经知道了模型的类型,或者说我们已经知道了这一个,或者说我们已经知道这个分布的类型,这个分布的风格,那么我们只需要预估这个分布的参数时候,这种情况是非常非常的简单的,但是现实生活中,对于一些具体的问题来说,我们往往是不知道他具体的一个模型的类型的,就比如说一个非常简单的, 0到9的一个数字识别,你能告诉我你是怎么识别出零?你是怎么识别出一的吗?或者说,你能告诉我你识别了这种方法,或者说mapping,他是几次方的几次方二次方三次方,还是N次方。很明显我们一无所知,因为我们人本身对我们人脑的一个工作模式,或者说对我们人的智能的一种模式都不是很理解,所以我们去解释深度学习的时候就发现我们解释不了?这也是合情合理的,OK,

    我们回到正题,至于说我们真实的这个分布,如果他是不知道的,我们不但连他的参数不知道,θ参数是不知道,连他的一个风格,连他的一个次方或说一个类型,我们都不知道。那么这种情况下面我们怎么来解决这一个问题呢?

    在这里插入图片描述
    我们不但是对px的类型不知道,而且我们观察的时候还会有一个观察的误差,对吗?就比如说,我们即使已经是知道了房价的面积,和以及房价的具体价格,那我们这个价格和面积,他一定是完整 的按照我们的w和b的参数进行设置的吗?很明显不是 。 每个地方,比如说你量面积的时候,就会有一个测量误差按你房价的时候也会有个取舍误差,或者说你做活动呀,然后不同的顾客类型呢,你都会有误差,我们把统一误差合并到一个因子上面去,比如说我们把这一个误差把这个噪音把它理解为抽象为一个复合一个分布的最简单的情况,就是说它符合一个均值近似于0的一个高斯分布 。这样子的话,我们拿到了数据,他有可能就不是真正正确的数据,它就包含了不同的类型的eps,eps的大小,还不太一样,只是他符合同一个分布,然后的话,这种情况下面,如果我们只用两个点来预估的话,它存在的噪声随机性是稍微比较大的,所以我们才需要更多的数据来做一个分布,而且如果你拿到一个少量点的话,你可能会觉得他不只是不是符合一个线性模型?对吗?因为只观测到了一个少量的样本,你可能觉得它的波动性比较大,这样子的话,你就不会优先尝试去用一个线性去预估它,你可能会用什么模型呢?
    在这里插入图片描述
    你可能会用wx的平方,加上bx+c这种模型去模拟他这个数据的分布,现在我们来对模型本身来做一个度量 什么意思呢?就是说我们用一个模型去学习到一个数据的分布的时候,我们会优先的选择不同类型的模型,就比如说对一个多像素来说,他们可能会使用一个常数,这样的模型去学习也有可能使用的一次方也有可能使用一个二次方,或者是最糟糕,遭到大使用一个高次方N次方N次方,那么不同类型的不同次方的一个多项式的模型,他代表图形,大家可以看得到,对于你高次方越高的话,他的这个抖动就越大,他的这个波形就越复杂,对嘛?我们来看一下怎么衡量不同类型的模型的一个这样的学习能力来我们把他叫来名字叫做model capacity,
    在这里插入图片描述
    基本上可以看到对一个常数的模型来说,她的学习能力是非常非常弱的,如果它基本上因为只有一个参数,所以说它能够学习到的这个参数非常少的,像当你的次方增加的时候增加了N次方的时候,你这个网络的表达能力更强了,你能够表达的那个分布的情况就更复杂了,对于一些非常非常复杂,非常抽象的一些映射,你也能够很好的学习到这种情况下面,我们就讲这个模型的表达能力变强了,也就是我们把它叫做model capacity也就这个模型的能力,capacity的容量变大了,或者说这个模型搜索空间变大了,只是说这个搜索空间,他因为是连续的,
    在这里插入图片描述
    现在的深度学习,当你变得越来越深,他从另外一个方面也反映了我们的model capacity能变得越来越大了,比如说你只有八层的时候,你的参数量可能是60M,然后当你19层的时候你参数可能是200多M,我是假设的,然后当你的参数量变成152层的时候,你这个时候你的显卡就需要很大很大显存,因此你这个参数可能是上GB这种情况下面你的参数量越大可能会更加类似于那种多项式的一个类别,你就多项式的次方就越高,因此你真的模型表达能力越强,只要你这个模型能够很好的优化的话,那你优化出来的最终一个结果,他肯定是比你一个19层的啊,比八层的一个学习能力是更强的,它能够抽象出一些更高维度的一些特征,能够做一些更高维的一个类比。

    在这里插入图片描述
    那我们看两种情况,

    第一种情况是什么呢?就是我们用的模型,我们estimated的是什么?

    我们用的模型的本身的一个capacity只有我们用的模型的一个表达能力小于他真实的一个模型的一个复杂度,这是什么意思呢?其实我们真实的,也不知道我们这里只是做一个非常形象,一个这样的比较。假设我们已经知道了,比如说我们这里的GPA的分布,
    我们已经知道了这个GPA的分布,它就是一个高斯分布,然后当我们知道了这个ground-truth,就是分布的一个复杂度的时候,我们用一个比较简单的这个简单的这个模型的复杂多,这个模型的能力比你真实的要少一些,这种情况就是我们这个案例里面讨论的情况,这种情况我们给它起一个名字,叫做under-fitting 。under到底的是什么呢?我们用的模型的复杂度会小于真实的一些数据的复杂度,这种情况会造成我们这个模型的表达能力不够,就好比你一个小朋友一样,你小朋友们的英语可能只学了一些基本的词汇量,词汇量可能就在三四百的样子,但是现实生活中,我们成人会说一个18岁,18岁小朋友,他们词汇量接近于一万左右,这样子的话,你一个七八岁小朋友跟一个18岁小朋友去聊天的时候,你会发现这个七八岁小朋友,他的表扬能是非常非常非常弱的,他只能说一些基本的词汇,它不能表达出一些很高级的情绪,这样子他就去跟18岁的小朋友,18岁的青年人沟通时,他就会有一个表达能力不足,

    还有另外一个例子就是现实中遇到例子,他在我们后面会讲的WGAN,
    在这里插入图片描述
    应该早期版本,他也是下来给约束,会把你模型的复杂都给约束下来,这样子的话,本来是一个比如说我们这里是一个八个高斯的mixed-model,你看一下是稍微来说比较漂亮,比较复杂,对不对?但是如果你对了这个模型的复杂度做了约束的话,导致你这个模型的表达你不够强,因此你学到了这个patient就是一些比较简单,比较直接的,他很可能就不能够表达这么复杂的,这么精美的一个结构出来。

    Under-fitting怎么体现出来呢Under-fitting就是说我们在training的时候呢?

    训练的精度和训练的loss都不是很令人满意,我们看一条曲线,比如说他出现是。你正常的一个比较好的training?然后你training的loss就会下降,对不对

    这些局限性比较好的一个情况?然后如果您属于under-fitting,你的精度,所以可能会出现什么呢?会一直到了这个情况也再也上不去了,就是你的training的精度,肯定会比较低,然后你training的loss以后在一个情况一直下不去,因此这个地方这两条线就叫做under-fitting ,然后同样的道理,你即使是training的test的精度、test的loss也会很差,因此对于under-fitting的话,就不大好检测,如果你的两个两项指标都不好,就你training的时候也train不好,test的时候更别说也train不好,这种时候你就会尝试着去把你的模型复杂度,会增加一下,就比如说你会堆叠更多的层数呀单元数量会增加,你通过这种方式增加了你模型的复杂度,以后你尝试着看这个情况是不是得到改善,如果得到改善,那意味着您之前的情况,那就是你的模型复杂度小于一些实际的数据和模型复杂度,这样子的话,你就需要增加你的模型的复杂度。

    在这里插入图片描述

    然后与刚刚

    under-fitting相反的就是另外一种情况是什么意思呢?

    我们来看一下,同样的是,对于这个GPA的例子,这个GPA的例子,我们很明显这条蓝色的线是比较圆滑的,可以勾勒出整个的一个GPA的一个重要分布的情况,这条颜色的线,大家有没有发现他他在train的时候?
    他除了比你这条线以更光滑以外,他开始慢慢地地慢慢地或者说每一种情况都勾勒出来,他会慢慢的接近于每一个点,会把每一个点都穿过,这种情况就是他过分的把这个噪声给包含进来了,你看一下边缘的情况,边缘的情况,他为了拟合你这个点它升值到这里来了,就是完全没必要,这种情况就是什么意思呢。

    就是说我们的使用的模型的复杂度是大于我们真实的模型复杂度,这样子他要train的时候,她训练就发现为了让你的loss更低,他就会尝试着去把每一个点的loss会降低这样子的话,他会去逼近于每一个点,大家发现没有,本来这条线走中间就可以了,但是为了让她的loss更低的话,他就开始穿过每一个点穿过每个点穿过每一个穿过每一点,这种情况会使得你的training的情况特别特别好,因为你现在看到这个黑色的点就是training的一点,对吗?他会穿过每一个点或尝试就是靠近每个点这样子的话,你training的时候的精度可能都会变的很好,但是如果我们test的点大家看一下这个test的点,
    在这里插入图片描述
    test的点也是随机散布出来的吧,他有可能跟train的点并不在同一位置,而且很有可能就不在同一位置,因为它是均匀的分布在俩侧,如果我们看一下对于红色的点,它是分布在这个位置的话,你去逼近这个点的时候,你就会远离这一点,对吗?你是毕竟这个点的时候,你就会远离这一个点,所以的话,它会造成一种情况就是在你训练的时候发现性能很好,但是你test的时候会做验证的时候就非常非常非常不好,这种情况就知道over-fitting,然后over-fitting表现出来就是我们刚刚讲的training的时候效果特别好,但是test的时候,效果不好,然后我们换了另外一个词,我们把over-fitting的话叫另外一个名字叫做什么?Generalization performance,也就是泛化能力,当你的over-fitting严重的时候,你的方法,能力都会变差,这种情况就是我们不想要看到的OK,我们来现场做一个总结,
    在这里插入图片描述
    如果你数据分布是一个这种分布的话,你用应该简单的模型,那就是under-fitting。用应该复杂的模型,那就是over-fitting,现实生活中更多的是over-fitting,因为我们现在的计算机的计算能力得更强了,我们能够优化的网络的复杂度会变非常非常的深,非常非常宽,这样子的话,你很容易网络表达能力就超过了你现在的一个模型的能力,这里需要区别一下,我们这里讲的模型的能力一般指的是在给定的,有限数量有些数据集在下面的一个模型的能力就是你数据集足够多的话,那可能他就不会over-fitting了,如果你数据集有限的话,那他因为包含了噪声,你就很容易很容易的over-fitting,所以的话,我们要解决两个问题,第一个是怎么检测over-fitting第二个是怎么减少over-fitting,我们在下一节课通过数据集之间划分来检测有没有over-fitting。

    展开全文
  • 全文超过26000字,建议收藏下来,以便后期翻阅学习,在讲解完什么是DP,附上了8道典型DP例题,覆盖了线性、区间、二维、四维等模型,最后简单说了下如何优化DP,虽然说不敢保证你把这8题弄懂后以后就能够在DP的题目...

    动态规划27k字超详细保姆级入门讲解

    在这里插入图片描述


    写在前面:

    这篇文章是目前为止我写过最长也是最久的文章,前面关于DP的讲解我查阅了大量的博客资料,学习其他博主对DP的理解,也翻阅了很多经典的纸质书籍,同时做了近十道DP后也融入了我自己对DP的理解,自己总结了一套DP题目的解题套路方法全文超过26000字,建议收藏下来,以便后期翻阅学习,在讲解完什么是DP,附上了8道典型DP例题,覆盖了线性、区间、二维、四维等模型,最后简单说了下如何优化DP,虽然说不敢保证你把这8题弄懂后以后就能够在DP的题目中叱诧风云,但我总结的解题方法和这8道模型多多少少都能对你以后遇到DP没思路时一点点的启发。

    因为文章比较长,下面附上目录,可以根据需要跳转:

    什么是DP

    首先要了解的是,和贪心算法一样,动态规划算法只是一种思想,不是像排序算法一样有具体的代码。

    一千个人有一千个阿姆雷特,每个人对DP的理解都是不同的,我第一次学习动态规划,是在《算法图解》这本书中。作者通过背包问题、旅游行程最优解、最长公共子串、最长公共子序列四个典型的案例来讲解动态规划。因此,我对DP的初体验是它是个将如何解决一个大问题拆解为如何解决一个个独立的子问题的想法。

    我觉得一上来没有必要给DP下个教科书式的定义,因为dddd(懂得都懂),不懂得看着学术的话语还是不懂,所以我更推荐直接做后面的8道经典例题,在实践中去体验真正的DP思想。下面我附上几个DP的相关术语(摘自百科),同样的,可以先不看,在后面题解提到相关概念时再返回来查看。

    阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。在多数情况下,阶段变量是离散的,用k表示。此外,也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的 。

    状态:状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主观意志为转移,也称为不可控因素。在上面的例子中状态就是某阶段的出发位置,它既是该阶段某路的起点,同时又是前一阶段某支路的终点 。

    无后效性:我们要求状态具有下面的性质:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路(所通过的点)的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性 。

    决策:一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。在最优控制中,也称为控制。在许多问题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史 。

    决策变量的范围称为允许决策集合 [6] 。

    策略:由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合 。

    允许策略集合中达到最优效果的策略称为最优策略 。

    给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k))与x(k+1)确定的对应关系,用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律,称为状态转移方程 。

    最优化原理:作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略” 。

    最优性原理实际上是要求问题的最优策略的子策略也是最优


    如何设计DP

    先上我自己总结的DP设计流程

    DP设计

    1.明确到底是几维的DP,是否有必要升级维数或降低

    2.如何将大问题化为小问题

    3.定义数组元素的含义,存放的数值的意义所在

    4.找出DP状态转移方程

    5.找出初始值、注意临界值,递推/递归总设计思路

    同样的,我会在具体的实例中展示这个流程的使用方法。下面的8道例题中有3道都是用这个方法设计DP算法的哦~


    经典例题:

    线性模型

    例题一、过桥问题

    题目:

    在一个夜黑风高的晚上,有n(n <= 50)个小朋友在桥的这边,现在他们需要过桥,但是由于桥很窄,每次只允许不大于两人通过,他们只有一个手电筒,所以每次过桥的两个人需要把手电筒带回来,i号小朋友过桥的时间为T[i],两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

    输入:

    两行数据:

    第一行为小朋友个数n

    第二行有n个数,用空格隔开,分别是每个小朋友过桥的时间。

    输出:

    一行数据:所有小朋友过桥花费的最少时间。

    样例:

    输入

    4
    
    1 2 5 10
    

    输出

    17
    

    问题分析:

    看到这题的时候感觉回到了小时候被奥数支配的痛苦中,在读完整个题目后,题意并不难理解,但是这也能用DP解???

    我估计看完题后,很多人的想法都和我一样,就是让那个最快的人充当“跑腿”的人传递手电筒,那这样子不就是答案了吗?每一次跑腿还有比这个更好的方法吗?这是典型的贪心算法,并没有考虑到整体的最优解。

    就以题目的样例讲解

    1 2 5 10

    如果按照贪心算法,

    第一次:1和2过桥,用时2,1再返回,用时1.

    第二次:1和5过桥,用时5,1再返回,用时1.

    第三次:1和10过桥,用时10,结束。

    共用时19分钟,虽然用贪心算法算出来的答案与答案很相近,但数据如果再大点就相距甚远了。

    那现在我们先停顿一下。究竟是什么原因造成了这样的“误差”呢?

    我们先来采访一下这名跑的最快的同学

    “我好累啊,明明可以跑很快的,但偏偏要等别人”

    嗯…

    就好像学霸被学渣拖累一样,挺辛苦的,印证了那句“不怕神一样的对手,只怕猪一样的队友”

    那我们可不可以调整下策略,每次都让走路速度相近的一起过桥呢,但每次送手电筒依旧肯定选最快的,就是把送手电筒和过桥分开考虑。

    嗯,也许到这里你已经有自己的想法了,可以先暂停一下,用DP的思维自己设计下算法,下面也会进行揭晓。

    深入解析

    在设计算法之前,我觉得我们还是要先弄清楚这道题的几个基本概念问题。

    假设共有N个小朋友要过桥,那么要过几次桥呢?(包括来回送手电筒的次数)

    答案是2N-3次,证明如下:

    将N个小朋友中的一个小朋友看成“跑腿”的,那么它需要将N-1个小朋友都送到河对岸,鉴于每次都要回来,故是2(N-1)次,由于最后一次跑腿人也一起过来了,(此时河对岸已经没有人了,就不用再回去啦)所以就是2(N-1)-1,也就是2N-3次

    再者,我们要决定过桥的顺序,~~尊老爱幼,是中华名族的传统美德让最小的小朋友先过河?~并不是,不用那么多戏,按过河速度从小到大过河把(当然…你也可以按先输入后输入的顺序过河,或者乱过,但思维量就要高很多了)

    最后,既然是DP问题,就要考虑状态转移方程了,假定现在按照过河速度的快慢过河,记他们每个人的过河速度为a[0]…a[i]…a[N],依次递增,到了第i(1<i<N)个小朋友过河,那么此时河的对岸已经有i-1个小朋友了。

    直击灵魂的问题:请问现在手电筒到底在河的哪一边?是过河的那一边,还是未过河的一边?

    机智的你肯定没有回答这个问题,因为我根本就没有说清楚呀,也就是说要分类讨论

    假定现在手电筒在对岸,那么我们让a[0]跑腿过来送手电筒,然后这时我们让i和i+1一起过河(因为他们是“实力相当的对手”走路的速度最接近,不会相互拖累),太棒了,这样子i和i+1都过河了,然后让a[1]送手电筒过来(因为此时只有它在河对岸且跑的最快)

    那么此时就很尴尬了,a[0]和a[1]都在”未过河“的一边,接下来是让i+2过河呢?还是将a[0]和a[1]先送回去先呢?

    停顿一下,思考一下。

    DP设计:

    答案是让将a[0]和a[1]先送回,因为我们的过河顺序是”谁跑的快谁先过河“(之所以a[0]送手电筒过去后不考虑它先过河是因为它此时的那个岸上没有和他”旗鼓相当的对手“)。

    看到这里应该就都懂了把,自己试着写下状态转移方程吧。

    ”等等…你不是说分类讨论么?另一种情况你好像没有说欸“

    ???你再好好看看我的分析,其实已经说过了

    下面上方程!!!两种情况选用时最短的那个

    dp[i] = min ( ( dp[i-1] + a[0] + a[i] ),( dp[i-2] + a[0] + a[i] + 2*a[1] ) )
    

    什么,你还是没弄懂?

    好吧,再提醒你一下,试着就以题目的

    1 2 5 10为例子,当i=3和i=4时看看。

    emmmm…那我就再保姆级别的讲解一下

    假设现在到了最后一个小朋友”10“过河,通过上面的分析我们知道它是和i-1,也就是”5“一起过河的,那么dp[i]就等于dp[i-2],就是”1“和”2“过河的时间,加上“1”送手电筒和”1“”2“一起回来的时间,这种情况是最优的,而不是前面的dp[i-1] + a[0] + a[i](因为此时0已经过去了)

    最后最后再讨论一下i的取值范围,肯定要大于3啦 不然i-2就越界了

    dp[1]=a[1]

    dp[2]=a[1]

    dp[3]=a[1]+a[0]+a[2]

    代码:

    #include <bits/stdc++.h>
    using namespace std;
    
    int a[50];
    int dp[51];
    
    int main()
    {
    	int n;
    	int i,j;
    	
    
    	//记录速度 
    	cin >> n;
    	for ( i=0; i<n; i++ )
    		cin >> a[i];
    		
    	//排序速度
    	sort ( a, a+n );
    	
    	//打表前几个数据 
    	dp[1]=a[1];
    	dp[2]=a[1];
    	dp[3]=a[1]+a[0]+a[2];
    	
    	for ( i=4; i<=n; i++ )
    	{
    		dp[i] = min ( ( dp[i-1] + a[0] + a[i-1] ),( dp[i-2] + a[0] + a[i-1] + 2*a[1] ) );
    	}
    	
    	cout << dp[n] << endl;	
    	return 0;
    
    }
    

    举报!!你的状态转移方程改了!嗯,是的因为我是从0记录速度的,所以到n这个人的时候他的速度应该对应回去i-1

    例题二、最长递增子序列

    题目:

    给定一个长度为n(1 <= n <= 1000)的整数序列a[i],求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列),满足如下条件:

    1、该序列单调递增;

    2、在所有满足条件1的序列中长度是最长的;

    问题分析:

    这道题是一维的(其实这道题也可以转化为用最长公共子串二维来解,但要去重)

    在理解完题意后,枚举固然是一种方法,只要把全部的可能性列出来然后逐一检查就能找到答案,但却不是可行的方法,因为2^(1000)是指数爆炸级别的。

    嗯,既然枚举这种方法是肯定不行的,那么这种算法其中有没有我们值得学习和借鉴的呢?

    有,通过这篇博客,我们可以大概把DP理解为记忆化的DFS,那么在枚举的过程中我们可不可以通过记忆减少复杂度呢?

    因为在传统的枚举过程中,每次枚举的情况,我们都要从头开始算它到底有多少符合条件的子序列,这也是为什么枚举的复杂度是2^(1000)。那我们每一次枚举可不可以站在巨人的肩膀上,从上一次枚举的已经记录下来的结果推导出来呢?

    那,这不就是DP的状态转移方程吗?

    如何设计呢?建议看到这里的你先暂停一下,自己思考设计下状态转移方程。下面进行解密。

    为了更形象一点,我先举个例子

    假设有数列

    1,4,6,3,8,2,9,11,2,60
    

    肉眼就能判断出最长递增子序列是

    1,4,6,8,9,11,60
    

    我们一开始从第一个数开始检索,无论第一个数多大,最长递增子序列到目前为止就是1(因为就它一个呀,没有大小之分),到第二个,就要判断它是否比1大了,如果大,恭喜!加入子序列,反之则不加入。

    假定我们用dp[i]来记忆截至到数列a[i]时的最长递增子序列

    那么,就很容易推算出,当检索到a[j]的时候dp[j]的值肯定是dp[0]-dp[j-1]的值中最大的那个+1(当然要符合递增条件的前提下)

    因为截至到每一个数时都有很多可能,比如当i为4时,他的子序列有

    1,4,6,3
    
    1,4,6
    
    1,4,3
    
    1,6,3
    
    ......
    

    但其中最长的且符合条件的只有1,4,6

    那么在i为5的时候,就可以看前面最大的dp是多少,然后如果i符合条件(递增条件)就+1,如果不符合条件,那它就没有任何价值了。

    代码示例:

    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
    	//测试用的数组 
    	int a[]={1,4,6,3,8,2,9,11,2,60,1};
    	int dp[10];
    	int i,j;
    	int len = sizeof (a) / sizeof (a[0]);
    	
    
    	//默认全部为1,就是以自己为起点 
    	for ( i=0; i<len; i++ )
    		dp[i] = 1;
    	
    	//一定要加上dp[j]<dp[i]+1的条件
    	//因为我们只要前面最大的那个dp,不加这个条件,只要大于就+1,那所有阿猫阿狗都符合条件了	
    	for ( j=1; j<len; j++ )
    		for ( i=0; i<j; i++ )
    			if ( a[j]>a[i] && dp[j]<dp[i]+1 )
    				dp[j] = dp[i]+1;
    	
    	int max = 0;			
    	for ( i=0; i<len; i++ )
    		if ( dp[i]>max ) max = dp[i]; 
    				
    	cout<<max; 
    
    }
    

    例题三:DIO的面包工坊

    题目:

    Dio是荒木庄的面包师傅,和手部美容师Bo良Ki影是好朋友。Bo良Ki影会在每个月的某一天来买注入爱心的小面包。面包的爱心总值是爱心小面包的乘积。这个月Dio会把n个爱心值分配到许多个爱心小面包中,为了给好朋友Bo良Ki影最大的爱心总值,他要如何分配呢?

    注意:爱心总值可能很大,请使用long long存储答案

    Input

    第一行输入一个整数T,表示有T组数据。(1<=T<=1000)

    每组数据输入一个整数n,表示Dio的爱心值。(1<=n<=100)

    Output

    每组数据输出一个整数,表示最大的爱心总值

    Sample Input

    2

    3

    5

    Sample Output

    3

    6

    问题分析:

    第一次看其实是有点蒙,不知道如何下手,这时也只能先列表咯,看看前几个数据有没有什么规律。

    1 2 3 4 5 6 7 8 9 10
    1 2 3 4 6 9 12 18 27 36

    这个难度应该不大,因为每个数字的组合有限。

    其实我们在列表的时候就发现了,后面的数首先要进行拆分,如9可拆为4+5或3+5,然后每一部分我们都要找出乘积最大的情况,那这时我们就要在列表中去前面找已经算过的最优解若是4+5,对应回去则是4x6,3+5对应回去3x6,故要应用递归函数。

    且状态转移方程为

    a[n] = max ( a[i] * a[n-i] ) 其中n>i>=1
    

    这时我第一次提交的代码如下:

    #include <stdio.h>
    #include <math.h>
    
    //用函数来解题
    long long int sum ( int n );
    
    int main()
    {
    	int t, n;
    	long long int ans;
    	
    
    	scanf ( "%d", &t );
    	while ( t-- )
    	{
    		scanf ( "%d", &n );
    		
    		ans = sum(n);
    		printf ( "%lld\n", ans );
    	}
    	
    	return 0;
    
    }
    
    //函数本体
    long long int sum ( int n )
    {
    	long long int total;
    	int mid;
    	int i, j;
    	
    
    	//n小于3时无需拆分 
    	if ( n<=3 )
    	{
    		total = n;
    	}
    	else
    	{		
    		mid = n/2;
    		
    //错误的代码 误以为中间分一半就一定是最大 
    		if ( n%2==0 )
    		{
    			total = sum(mid)*sum(mid);
    		}
    		else
    			total = sum(mid)*sum(mid+1);
    	}
    	
    
    	return total;
    
    }
    

    很显然,上面的代码并没有通过,原因是误以为中间分一半就一定是最大。其实上面的9就可以证明,分成3+3+3时才是最大。

    简单修改后如下

    	total = sum(1)*sum(n-1);
    	
    	//把n的所以拆分情况列出并递归求解 
    	for ( i=1; i<=mid; i++ )
    	{
    		if ( total < sum(i)*sum(n-i) )
    			total = sum(i)*sum(n-i);
    	}
    

    虽然修改后符合条件,但很遗憾的是大大超时了,拆分情况有很多种,每一种又有很多次递归操作,故时间复杂度很大。

    那证明其实我的算法还是有问题,要如何调整呢?

    AC代码:

    #include <stdio.h>
    #include <math.h>
    
    //全局变量自动初始化为0 
    long long int a[101];
    long long int sum ( int n );
    
    int main()
    {
    	int t, n;
    	long long int ans;
    	
    	scanf ( "%d", &t );
    	while ( t-- )
    	{
    		scanf ( "%d", &n );
    		
    		ans = sum(n);
    		printf ( "%lld\n", ans );
    	}
    	
    	return 0;
    
    }
    
    //函数本体
    long long int sum ( int n )
    {
    	long long int total;
    	int i, j;
    
    	//n小于3时无需拆分 
    	a[1] = 1;
    	a[2] = 2;
    	a[3] = 3;
    			
    	if ( n<=3 )
    		return a[n];
    	else
    	{
    	//讲数组先一步步以123数组递归算好,然后直接输出就好。
    	//其实还有优化的空间
    	//把这个放在main函数里面就好,这样子不用每次都算数组,算一次就好。
    	//后面的几次会浪费一点点时间,但好在没超时
    		for (int i=4; i<=100; i++)
    		{
    		//只用i/2即可,因为另一半就是i-j
    			for (int j=1; j<=i/2; j++)
    			{
    				if (a[i] <= a[j] * a[i-j])
    					a[i] = a[j] * a[i-j];
    			}
    		}
    		
    		total = a[n];
    	}
    	
    	return total;
    
    }
    

    区间模型:

    例题四、插入回文串

    题目:

    给定一个长度为n(n <= 1000)的字符串A,求插入最少多少个字符使得它变成一个回文串。

    问题分析:

    一开始看到这个题目的时候,最先让我想到的是之前写过的一道题目最长回文子序列(其实是可以用那道题的二维DP思路解这道题,后面会补充说明,但我先讲解下区间模型)

    也许你并不知道如何通过插入最少的字符来使原序列变成一个回文序列,这时候我门不妨换个角度思考下(这也是在做题遇到没思路时的一个小技巧),你肯定知道如何增添字符让一个回文串依旧是回文串,或者让一个回文串不再是回文串。

    在这之前,我们先要了解回文序列的特征,当一个序列是回文序列时,如果这个时候我们一定要对其进行增添的操作时,当且仅当在序列的正中间添加一个或者在两边对称添加相同的字符时它还是回文序列,其他的情况(不对称添加或者单个添加)都会使这个回文序列失去回文序列。

    也许你会问,这个和题目有什么关系呢?别急,待我慢慢叙说。

    我们知道DP的本质是将大问题化为一个个的小问题去解决,那么区间模型就是把大区间逐渐化为小区间去解决,由于回文串的特征,故这个区间是对称缩小的,就是从两边逐渐缩小到中间,而不是单一方向的缩小,如从左缩到右或者从右缩到左(这句话的意思就是有些区间模型是单方向缩小的咯)。

    嗯,还是以例子来说明吧。

    abc,bad
    

    这个序列要如何修改呢?

    假设s[i]表示第i个字符。(从1开始计数)

    长度并不长,第一眼看上去也许你会尝试多种可能的情况,对比后得出答案,但我现在带你用DP来解下这道题目

    刚刚我们说过这道题要从两边向中间缩,

    也许你不知道s[1]到s[7]这串序列的解法,但你不妨先判断下s[1]和s[7]它们各自的值是否相等,如果相等,不就符合我们刚刚所说的回文序列的特征吗?左右刚好对称

    如果不相等,因为我们的目标是要让它变成回文,故我们要进行增添操作,刚刚我们又讲过

    当且仅当在序列的正中间添加一个或者在两边对称添加相同的字符时它还是回文序列

    故我们有两个选择,一个是

    在s[1]的左边添加一个值,使它与s[7]一样,

    或者在s[7]的右边添加一个值,使它与s[1]一样

    选那种呢?当然是选添加最少的那种啦?

    也许你会问,这两种情况不是都添加一个值吗?为什么会有多少的问题。

    嗯,小朋友,你再思考下,现在我们是不是值判断了最左和最右是否构成了回文的结果啊,中间还有s[2]到s[6]我么没有判断呢~

    可以先暂停思考一下,自己设计DP状态转移方程,下面给答案:

    dp[i][j] = min( dp[i+1][j]+1, dp[i][j-1]+1  )
    

    代码分析:

    #include <bits/stdc++.h>
    using namespace std;
    
    char s[1002];
    int dp[501][1001];
    
    int palindrome( int i, int j )
    {
    	if ( i>=j )
    		return 0;
    	if ( s[i] != s[j] )
    		dp[i][j] = min( palindrome(i+1,j)+1, palindrome(i,j-1)+1  );
    	else
    		dp[i][j] = palindrome(i+1,j-1);
    		
    
    	return dp[i][j];
    
    }
    
    int main()
    {
    	scanf ( "%s", s+1 );
    	int len = strlen(s+1);
    	
    	cout << palindrome(1,len) << endl;
    
    }
    

    其实上面的代码只能通过一半的测试点,剩下一半的测试点会因为超时而不通过,我在之前的博客有分析递归超时的原因以及解决方法和优化方案,这里就不赘述了,没看过的朋友可以先看看
    递归超时怎么办?递归与递推的区别?递归的优化之道

    对的,上面有太多重复计算的过程了,可以用记忆化减少计算次数,代码如下:

    #include <bits/stdc++.h>
    using namespace std;
    
    char s[1002];
    int dp[600][1001];
    
    int palindrome( int i, int j )
    {
    	if ( i>=j )
    		return 0;
    	if ( dp[i][j] >= 0 )
    		return dp[i][j];
    	if ( s[i] != s[j] )
    		dp[i][j] = min( palindrome(i+1,j)+1, palindrome(i,j-1)+1  );			
    	else
    		dp[i][j] = palindrome(i+1,j-1);			
    		
    
    	return dp[i][j];
    
    }
    
    int main()
    {
    	memset(dp,-1,sizeof(dp));
    	scanf ( "%s", s+1 );
    	int len = strlen(s+1);
    	
    
    	cout << palindrome(1,len) << endl;
    
    }
    

    另一种记忆化写法:

    #include <bits/stdc++.h>
    using namespace std;
    
    char s[1100];
    int dp[1100][1100];
    int mark[1100][1100];
    	
    int palindrome( int i, int j )
    {
    	if ( i>=j )
    		return 0;
    	if ( mark[i][j] == 1 )
    		return dp[i][j];
    	if ( s[i] != s[j] )
    	{
    		dp[i][j] = min( palindrome(i+1,j)+1, palindrome(i,j-1)+1  );
    		mark[i][j] = 1;
    	}			
    	else
    	{
    		dp[i][j] = palindrome(i+1,j-1);
    		mark[i][j] = 1;	
    	}
    				
    		
    
    	return dp[i][j];
    
    }
    
    int main()
    {		
    	scanf ( "%s", s+1 );
    	int len = strlen(s+1);
    	
    
    	cout << palindrome(1,len) << endl;
    
    }
    

    方案二:二维DP

    在开头的时候就点了一下,可以用传统的二维DP来做,整体思路就是先求出改字符串的最大回文子序列,保证这个结构不变,然后对那些不对称的零散的字符进行对称添加就好了,关于如何求最大回文子序列,之前有专门写文章说过,证明过程也很详细,这里就不赘述了,如果还是不懂,可以看下这篇文章。代码也在下面,同样AC了。

    最长回文子序列

    #include <bits/stdc++.h>
    using namespace std;
    
    char s[1001];
    char reverse_s[1001];
    int dp[1001][1001];
    
    int main()
    {
    	scanf ( "%s", s+1 );
    	
    
    	int len = strlen(s+1);
    	int i, j;
    	for ( i=1; i<=len; i++ )
    	{
    		reverse_s[i] = s[len-i+1];
    	}
    	
    	for ( i=1; i<=len; i++ )
    		for ( j=1; j<=len; j++ )
    			if ( reverse_s[i] == s[j] )
    				dp[i][j] = dp[i-1][j-1]+1;
    			else
    				dp[i][j] = max( dp[i-1][j], dp[i][j-1] );
    				
    	cout << len-dp[len][len] << endl;
    	return 0;
    
    }
    

    二维模型:

    例题五、psd面试——最长回文子序列

    题目:

    链接:https://ac.nowcoder.com/acm/contest/90/D
    来源:牛客网

    题目描述:

    掌握未来命运的女神 psd 师兄在拿了朝田诗乃的 buff 后决定去实习。

    埃森哲公司注册成立于爱尔兰,是一家全球领先的专业服务公司,为客户提供战略、咨询、数字、技术和运营服务及解决方案。他们立足商业与技术的前沿,业务涵盖40多个行业,以及企业日常运营部门的各个职能。凭借独特的业内经验与专业技能,以及翘楚全球的交付网络,他们帮助客户提升绩效,并为利益相关方持续创造价值。埃森哲是《财富》全球500强企业之一,目前拥有约41.1万名员工,服务于120多个国家的客户。于是psd打算去埃森哲公司投一下简历。

    于是他用英文写了一篇简历,由于手速太快了以致自己都不知道写了什么。
    然而面试官 xwc 一眼就看到了重点:大学打过 ACM!
    xwc:“
    听说你很低袄?考你个题:
    忽略字母大小写,你这篇简历去掉最长的回文子序列后还有多长?

    psd 顺手就把这个问题抛给了你。

    输入描述:

    多组输入,每组输入一个长度不超过 1234 的没空格的字符串,是 psd 的简历。
    

    输出描述:

    每组输出一个整数,如题。
    

    示例1

    输入

    google
    

    输出

    2
    

    示例2

    输入

    aBc,bAd
    

    输出

    2
    

    问题描述:

    头有点犯疼了,长度为1234的字符串,其子序列长度有21234之多,即1038次方之多,绝对会超时啊!那这要怎么去判断最长回文啊?

    说到回文,其实这个我是会判断的,就是先判断子序列是奇数还是偶数来定位中间,然后对半砍,对前一半用一个数组记录,然后对另一半反向运用数组检验就好了。

    最后的结果只需要根据回文长度和sizeof就可以得出。

    那么现在的问题就落到了子序列的问题,那么大的可能性肯定是因为算法不对,那么怎么才能寻找最长的回文子序列呢?

    这不就是典型的动态规划吗?!!

    之前由详细讲解过DP,其中的案例就是讲解最长公共子串和子序列,这道题并没有第二个对象,那么如何才能去匹配从而找到最长子序列呢?可以先思考下,下面揭晓答案。

    如何设计动态规划?我们用讲的方法来操作下

    DP设计

    1.明确到底是几维的DP,是否有必要升级维数或降低

    2.如何将大问题化为小问题

    3.定义数组元素的含义,存放的数值的意义所在

    4.找出DP状态转移方程

    5.找出初始值、注意临界值,递推/递归总设计思路

    问题一:

    借助回文序列的特性,讲原数组反转后就是对象啦,所以就是二维

    问题二:

    逐个逐个字符检验

    问题三:

    到该字符为止,匹配的字长回文子序列

    问题四:

    if ( c1[i] == c2[j] )
    	dp[i][j] = dp[i-1][j-1]+1;
    else
    	dp[i][j] = max(dp[i][j-1], dp[i-1][j] );
    

    问题五:

    预留开头一行和一列,防止状态转移方程数组越界,即第一个格子就是1,1了 而不是0,0

    下面以aBc,bAd讲解算法(要逐行填充不要逐列填充,详细原因可见这里

    a B c , b A d
    d 0 0 0 0 0 0 1
    A 1 1 1 1 1 1 1
    b 1 2 2 2 2 2 2
    , 1 2 2 3 3 3 3
    c 1 2 3 3 3 3 3
    B 1 2 3 3 4 4 4
    a 1 2 3 3 4 5 5

    是的,如果要判断最长公共子序列,那么横轴数轴就是各自的字符。这题要判断最长回文子序列,我们知道,只要子序列的左半部分和右半部分镜像对称,那么它就是回文子序列,既然是镜像对称,那我们把这个序列反过来,它一定会与原序列一一对应。

    如果你还没有弄懂,我举个例子,abcd1234321efghi这个序列,用眼睛一瞅就知道最长回文子序列为1234321,那我们把它取反后为ihgfe1234321dcba,发现没有!除了回文子序列的其他字符都受到了影响,而只有回文子序列没有被影响!

    AC代码:

    #include <bits/stdc++.h>
    using namespace std;
    #define jl 1500
    
    char c1[jl],c2[jl];
    int dp[jl][jl];
    
    void zh(char *a, int len)
    {
    	for ( int i=0; i<len; i++ )
    		if ( a[i] >= 'A' && a[i] <= 'Z' )
    			a[i] += 32;		
    }
    
    int main()
    {
    	int i,j;
    	while ( ~scanf("%s", c1+1) )
    	{
    		int len = strlen(c1+1);
    		
    
    		//将大写统一转换为小写	
    		zh(c1+1,len);
    		//将c1取反放入c2 
    		for ( i=1; i<=len; i++ )
    			c2[i] = c1[len-i+1];
    		
    		//特别重要,全局归零,每次都要重置
    		memset ( dp, 0, sizeof(dp) ); 
    		
    		for ( i=1; i<=len; i++ )
    			for ( j=1; j<=len; j++ )
    			{
    				if ( c1[i] == c2[j] )
    					dp[i][j] = dp[i-1][j-1]+1;
    				else
    					dp[i][j] = max(dp[i][j-1], dp[i-1][j] );
    			}
    		
    		cout << len-dp[len][len] << endl;
    		memset ( c1, 0, sizeof(c1) );
    		memset ( c2, 0, sizeof(c2) );
    	}
    	return 0;
    
    }
    

    例题六:最小路径和

    题目:

    题目链接

    难度中等

    给定一个包含非负整数的 *m* x *n* 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

    **说明:**每次只能向下或者向右移动一步。

    示例 1:

    输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
    输出:7
    解释:因为路径 1→3→1→1→1 的总和最小。
    

    示例 2:

    输入:grid = [[1,2,3],[4,5,6]]
    输出:12
    

    提示:

    • m == grid.length
    • n == grid[i].length
    • 1 <= m, n <= 200
    • 0 <= grid[i][j] <= 100

    错因分析:

    注意:下面是我个人在第一次写题目时用贪心算法的错误分析,如果你想直接看如何DP设计,可以直接跳到下一级标题。

    说实话,这道题真的卡了我很久,上周六就卡住了,自己真的想了很久为什么不能用贪心,到底哪里出了问题。

    这道题目如果按照题目的要求直接从左上角往右下角走,最后肯定是算不出答案的。因为如果从左上角开始走,每次都即走最小的那个方向的路劲时,就忽略了整体的最优解。如这题的结果就会是1 -> 1 -> 4 -> 2 -> 1。但如果你从右下角开始考虑,因为每一个格子的来向有且只有两个,即上方和左方,所以就直接比较两者谁大谁小就好了。

    疑惑的点也就在此处。我们知道DP是一种类递推,记忆化dfs的算法,在设计DP的时候我们在一般情况下都是从下往上,从小往大递推的,有时候为了提高代码的可阅读性,我们会借助递归来反向实现DP的递推。

    关于递归和递推的区别,我之前有写过文章,我copy过来给不清楚的朋友看看

    注意,我觉得这里要先特别区分一下递推和递归的区别,虽然只有一字之差,但意思和本质却截然相反。从小学数学的时候其实我们就已经接触了递推,就姑且还以斐波那切数列为例吧,我们只有知道了前面几项,比如1、2才能推第三项的值,只有知道了第三项和第四项的值才能推出第五项…以此类推递推到我们需要求的那个项,有点类似于滚大雪球吧,只能从小雪球滚起。

    而递归呢,方向就是相反的(但最后求解过程中又包括递推),先告诉你,我要求第100项的值,嗯,这时候你就说“只要我知道第98项和第99项我就能求出第100项”,紧接着“只要我知道第97和98项我就能求出第99项”…等等等等这样一直把大问题(求第100项的值)逐渐化解为小问题(第99、98、…、1项的值),从上往下递归,直到递归到最低,也就是第一项时停止,然后原路一层层的把数值返回,从第一项第二项求出第三项,返回求出第四项(这里不就是递推吗)所以我更倾向于把递归理解为反向索引+递推。

    总结来说递推就是自底向上,从下往上求解,而递归是从上往下,触底反弹,返回答案。

    嗯,可能你已经有点感悟了,其实在大部分情况下递归都能用递推来实现,甚至在某些情况下递推还要更好,因为递推是记忆化的,而递归要看你如何设计了,如果不是记忆化的递归,那么每次都要触底才能反弹,也未免太浪费时间了。是的,在有时候碰到数据很大的时候,用递归固然可以直接解放你的思维量,让代码看上去很简洁,也易于别人阅读和修改,但随之而来的可能是空间的极度浪费或者根本就不够用啊,这时候你就要用递推了

    因为之前写过二维DP,也是路径问题过河卒,当时在写那到题目的时候就是在列出DP状态转移方程后用递推AC的,所以一开始在解这道题目的时候很自然的推出DP状态转移方程后就想用递推防止超时。

    当时觉得乍一眼一看,无论是递归还是递推不都是先判断哪个方向小,然后走哪边并记录结果吗?可是正向走得到的答案就是错的,如这题的结果就会是1 -> 1 -> 4 -> 2 -> 1。

    其实我估计大佬看到这里不禁一笑,早已看出问题所在了。

    其实我上述说的递推的核心并不是动态规划啊,它的算法本质是贪心算法,连算法都改了,那当然答案是错的。

    也许你看到这里还是很懵,没事,下面我会详细分析原因的。

    先推荐看下我之前写过的贪心和动态规划的区别

    好,假设你看完啦,为了更生动的讲解原因,为此我设计了一个数组举例。

    1 3 1 3
    1 5 2 3
    4 6 4 3
    7 5 1 6

    如果按照我刚刚说的贪心递推,走的路径就是上图着重标记的数字,结果是23

    但实际…告诉你答案把,最小是19,方向如下:

    1 3 1 3
    1 5 2 3
    4 6 4 3
    7 5 1 6

    是的,也许你已经微微感受到了,贪心太短视了,虽然每一步选择的方向都是最优,但也仅是局部而已。

    回到问题,为什么贪心不行呢?

    我们看看贪心算法它解决了什么问题,抽出来一小块区域,同样标记出了贪心的走法

    1 5 2
    4 6 4
    7 5 1

    当从左上角的1走到最右边的4时候,我们一步步来分析,从1开始,要么下要么右,这时候我们选下,没错,这个决定并没有问题,问题出在与它解决的对象不是题目的问题,它只能保证到6这个点时候,你往下走比往右走路径小,嗯,仅此而已,因为要么1+5+6要么1+4+6,当你的问题是从1走到6怎么走最短时,贪心的确是对的。也就是说贪心的范围是很狭小的,只有4个格子的范围,而一般数组都不止2x2(因为本来贪心解决的就是局部最优解问题 只是在有些题目中 局部的最优解恰好是整体最优解,或者像旅行问题根本无法快速解决时由于贪心的结果和真正的答案很相近我们用局部最优解以优化时间为代价近似代替整体最优解)也许你现在还是不理解,我们再往下看看。

    还是上面这个小区域,从1到右边的4最优走法应该是1 -> 5 -> 2 -> 4

    当我们走到6时,若用贪心,我们只能确保从6走到右下角的1时的最优走法。

    因为我们不能保证每一次都是走斜右下角的路线,故连起来的最优解就不成立了,同理,将数盘扩大后就更加不正确了。

    DP设计

    设计没思路?按照我之前总结的一般解题方法套来看看有没有效果把

    DP设计

    1.明确到底是几维的DP,是否有必要升级维数或降低

    2.如何将大问题化为小问题

    3.定义数组元素的含义,存放的数值的意义所在

    4.找出DP状态转移方程

    5.找出初始值、注意临界值,递推/递归总设计思路

    问题一:

    那肯定时二维呀,图都给你画好了,不仅画好了,二维数组都给你定义好了,当然,有些大神用一维就可以AC这道题,有空以后可以讲讲(其实是现在我的水平不够hhh)。

    问题二:

    上面已经说过了,可以一步步扩大范围,知道到达右下角

    问题三:

    dp[i][j]
    

    存放的值肯定就是到i,j这个点的最小路径和啦~

    问题四:

    整个DP最难,也是最核心的部分,我们知道dp[i][j]的值取决于dp[i-1][j]和dp[i][j-1]的值
    因为我们只能从上方或者右方到达i,j整个点
    又因为题目要求最小,故选两者最小的一个
    故方程为 dp[i][j] = min ( dp[i-1][j], dp[i][j-1] ) + grid[i][j]
    

    问题五:

    如果你之前看过我写的过河卒,你肯定会直呼,有临界情况!!因为当时我就被临界情况活活折磨死了hhhh,就是第0列和第0行要特殊考虑

    啊,有点累,休息一会,下面给AC代码,可以先暂停自己敲敲看看~

    AC代码:

    int minPathSum(int** grid, int gridSize, int* gridColSize){
        int i,j;
        int dp[gridSize][gridColSize[0]];
        dp[0][0] = grid[0][0];
    
        for ( i=1; i<gridColSize[0]; i++ )
            dp[0][i] = dp[0][i-1] + grid[0][i];
        for ( i=1; i<gridSize; i++ )
            dp[i][0] = dp[i-1][0] + grid[i][0];
    
        for ( i=1; i<gridSize; i++ )
            for ( j=1; j<gridColSize[0]; j++ )
                dp[i][j] = fmin ( dp[i-1][j], dp[i][j-1] ) + grid[i][j];    
    
        return dp[gridSize-1][gridColSize[0]-1];
    }
    

    例题七:过河卒

    原题链接:传送

    题目描述

    棋盘上 AA 点有一个过河卒,需要走到目标 BB 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

    棋盘用坐标表示,AA 点 (0, 0)(0,0)、BB 点 (n, m)(n,m),同样马的位置坐标是需要给出的

    现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

    输入格式

    一行四个正整数,分别表示 B 点坐标和马的坐标。

    输出格式

    一个整数,表示所有的路径条数。

    输入输出样例

    输入 #1

    6 6 3 3
    

    输出 #1

    6
    

    说明/提示

    对于 %100 的数据,1≤n,m≤20,0≤ 马的坐标 ≤20。

    问题分析:

    第一个错误是错在题意的理解上面,虽然这道题的背景是中国象棋,但是在看到卒过河后只能向下和向右时就有点怀疑,到底是为了防止陷入左右左右左的死循环,还是为了提醒我们这不是中国象棋的规则呢。

    结果就是我想多了,对后面马的行走方式“跳跃一步”我以为就是上下左右的一步而已,而不是日字走法,其实还忽略了图的重要性,图中已经标明了马的控制点位置。

    第二个困难就是这是我第一次用C++写题,还有一些语法的问题。

    这是我第一次写的代码

    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main(){
    	
    
    	int x1,x2,y1,y2;
    	int i,j;
    	
    	cin >> x1;
    	cin >> y1;
    	cin >> x2;
    	cin >> y2;
    	
    	vector< vector<long long int> > a(x1+1);
    	for ( i =0; i<(x1+1); i++ )
    	{
    		a[i].resize(y1+1);
    	}
    	
    	for ( i=0; i<(x1+1); i++ )
    	{
    		a[i][0] = 1;
    	}
    	for ( j=0; j<(y1+1); j++ )
    	{
    		a[0][j] = 1;
    	}
    	
    	for ( i=1; i<(x1+1); i++ )
    		for ( j=1; j<(y1+1); j++ )
    		{
    			a[i][j] = a[i-1][j] + a[i][j-1];
    		for ( i=x2-1; i<=(x2+1); i++ )
    			for ( j=y2-1; j<=(y2+1); j++ )
    				a[i][j] = 0;
    		}
    	
    	cout << a[x1][y1];
    	return 0;
    
    } 
    

    其实这个很容易就可以得出状态转移方程,即

    a[i][j] = a[i-1][j] + a[i][j-1];

    然后因为之前有数组越界的经验,所以就将第一行和第一列都初始化为1,从1,1开始算起(其实这里就错了,因为可能第一行和第一列中就有马的控制点,又因为卒不能上走,故若在第一行控制点的右边全为0),马的行走方式也误认为是上下左右一格,每写完一个的数值后动态刷新马控制点为0.

    还是普通的数组了(以最大数值情况创建数组),也改正了马的行走方式,依旧采用每次写入都动态刷新控制点的做法,代码如下:

    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    int fx[]={0,-2,-2,-1,-1,1,1,2,2};
    int fy[]={0,1,-1,2,-2,2,-2,1,-1};
    long long int a[21][21];
    int i,j;
    
    void reset(int x2, int y2);
    
    int main(){
    	int x1,x2,y1,y2;
    	
    	cin>>x1>>y1>>x2>>y2;
    	
    	for ( i=0; i<(x1+1); i++ )
    		a[i][0]=1;
    	for ( i=0; i<(y1+1); i++ )
    		a[0][i]=1;
    		
    	for ( i=1; i<(x1+1); i++ )
    		for ( j=1; j<(y1+1); j++ )
    		{
    			a[i][j] = a[i-1][j] + a[i][j-1];
    			reset(x2,y2);
    		}
    	
    	cout<<a[x1][y1]<<endl;
    	
    	return 0;	
    } 
    
    void reset(int x2, int y2){
    	for ( i=0; i<9; i++ )
    		{
    			a[x2+fx[i]][y2+fx[i]] = 0;
    		}
    }
    

    虽然这次解决了马行走方式的问题,但还是没有解决一个问题,就是因为可能第一行和第一列中就有马的控制点,又因为卒不能上走,故若在第一行控制点的右边全为0。

    那么现在我的问题就是如何找到新的算法解决第0行和列越界的情况,最终还是求助于洛谷的题解,看了别人的解法后都然大悟!!

    既然我要解决越界问题,其实直接判断这到底是不是第0行或列,然后揪出来特殊处理不就好了。题解的方法十分巧妙,将状态转移方程直接拆成两个部分,分别对应行和列。

    题解中还解决了一个我很担心的问题,缩短了时间复杂度,就是每次的reset,在我上面的解法中,我每次通过状态转移方程写入数据时都要把马的9个控制点重新归零,要1个循环,九个步骤,特别担心超时。但题解中直接利用bool数组记录,只用循环一次即可,同时为了防止越界,也限制了条件在前。

    AC代码:

    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    //马的9个控制点 
    int fx[]={0,-2,-2,-1,-1,1,1,2,2};
    int fy[]={0,1,-1,2,-2,2,-2,1,-1};
    //只有BP[0][0]被赋值为1,其余均为0,这是全局变量的特性 
    long long int BP[21][21]={1};
    //同样利用的是全局变量的特性
    //但因为这个其实和最后的运算相反,需要再用到!
    //当然,也可以这里做处理,for循环赋初始值为1 
    bool MARK[21][21]; 
    
    int main(){
    	int x1,x2,y1,y2;
    	int i,j;
    	
    
    	cin>>x1>>y1>>x2>>y2;
    	
    	//通过MARK数组记录马的9个控制点 
    	for ( i=0; i<9; i++ )
    	{
    		//if判断是为了防止数组发生越界,只能在表盘范围内的点,越界就不管啦 
    		if ( x2+fx[i]>=0 && x2+fx[i]<=x1 && y2+fy[i]>=0 && y2+fy[i]<=y1 )
    			MARK[x2+fx[i]][y2+fy[i]] = 1;
    	}
    	
    	for ( i=0; i<=x1; i++ )
    		for ( j=0; j<=y1; j++ )
    		{
    			if(i)
    				BP[i][j] += BP[i-1][j];
    			if(j)
    				BP[i][j] += BP[i][j-1];
    			//特别重要的一个地方!
    			//当该点被刚刚标记为控制点后,就要归零,这里用的是乘法 
    			BP[i][j] *= !MARK[i][j];
    		}
    			
    	cout<<BP[x1][y1];
    	return 0;		
    
    } 
    

    四维模型

    例题八、方格取数

    题目:

    原题链接:传送

    设有 N \times NN×N 的方格图 (N \le 9)(N≤9),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字 00。如下图所示(见样例):

    A
     0  0  0  0  0  0  0  0
     0  0 13  0  0  6  0  0
     0  0  0  0  7  0  0  0
     0  0  0 14  0  0  0  0
     0 21  0  0  0  4  0  0
     0  0 15  0  0  0  0  0
     0 14  0  0  0  0  0  0
     0  0  0  0  0  0  0  0
                             B
    

    某人从图的左上角的 AA 点出发,可以向下行走,也可以向右走,直到到达右下角的 BB 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 00)。
    此人从 AA 点到 BB 点共走两次,试找出 22 条这样的路径,使得取得的数之和为最大。

    输入格式

    输入的第一行为一个整数 NN(表示 N \times NN×N 的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的 00 表示输入结束。

    输出格式

    只需输出一个整数,表示 22 条路径上取得的最大的和。

    输入输出样例

    输入 #1复制

    8
    2 3 13
    2 6  6
    3 5  7
    4 4 14
    5 2 21
    5 6  4
    6 3 15
    7 2 14
    0 0  0
    

    输出 #1复制

    67
    

    说明/提示

    NOIP 2000 提高组第四题

    问题分析:

    嗯,当时在写这道题目的时候第一眼看上去,这不就是两次最大路径和嘛?两次二维DP应该能解决。但打代码前还是以例题试试对不对吧,下面是DP表格

    0 0 0 0 0 0 0 0
    0 0 13 13 13 19 19 19
    0 0 13 13 20 20 20 20
    0 0 13 27 27 27 27 27
    0 21 21 27 27 31 31 31
    0 21 36 36 36 36 36 36
    0 35 36 36 36 36 36 36
    0 35 36 36 36 36 36 36

    可知走21 -> 15是最大的走法,第二次DP用眼镜一瞪就知道13 -> 14 -> 4是最大的,嗯 好像没问题,然后就叫上了自己的 first blood

    #include <bits/stdc++.h>
    using namespace std;
    
    int a[10][10];
    int dp[10][10];
    
    int main()
    {
    	int n;
    	cin >> n;
    	int x,y,num;
    	int sum=0;
    	
    	//载入数据
    	while ( 1 )
    	{
    		scanf ( "%d %d %d", &x, &y, &num );
    		if ( !x && !y && !num )
    			break;
    		a[x][y] = num; 
    	}
    	
    	//第一次DP
    	int i,j;
    	for ( i=1; i<=n; ++i )
    		for ( j=1; j<=n; ++j )
    			dp[i][j] = max( dp[i-1][j] , dp[i][j-1] ) + a[i][j];
    			
    			
    	sum += dp[n][n];
    	
        //删除数据
    	i=n;
    	j=n;
    	while ( i!=1 && j!=1 )
    	{
    		if ( i==1 || j==1 )
    		{
    			if ( i==1 )
    				j = j-1;
    			if ( j==1 )
    				i = i-1;
    		}
    		else
    		{
    			i = dp[i-1][j] >= dp[i][j-1] ? i-1 : i;
    			j = dp[i-1][j] >= dp[i][j-1] ? j : j-1;
    		}
    		a[i][j] = 0;
    	}
    	
    	//第二次DP
    	for ( i=1; i<=n; ++i )
    		for ( j=1; j<=n; ++j )
    			dp[i][j] = max( dp[i-1][j] , dp[i][j-1] ) + a[i][j];
    			
    	sum += dp[n][n];
    	cout << sum << endl;
    }
    

    题目好恶毒,竟然不是特殊情况,虽然过了题目的答案67,但提交到平台,五个测试点只对了一个.哎 题目的示例果然是干扰你的

    为什么两次DP就不行呢?我们再来回顾一下我们的流程,即第一次找出原棋盘的最大路径和,然后置0修改后,对修改后的棋盘求第二次的最大路径和.

    的确,两次DP的结构都是对应棋盘的最大路径和.

    但是你好像没有办法证明

    原棋盘最大路径和 + 第一次修改后棋盘最大路径和 = 两次原棋盘最大路径和

    因为不可控的因素太多了,两者相加的值就是答案

    再说通俗一点就是,两次的局部最优解并不一定是整体最优解.

    那现在自然而然就很容易想到,我们要如何设计才能达到最优解实现同时考虑两者情况呢?

    回忆你刚刚看到的文章标题,没错,四维DP.

    没思路?按照我之前说的DP设计方法套一套吧

    DP设计

    1.明确到底是几维的DP,是否有必要升级维数或降低

    2.如何将大问题化为小问题

    3.定义数组元素的含义,存放的数值的意义所在

    4.找出DP状态转移方程

    5.找出初始值、注意临界值,递推/递归总设计思路

    问题一:

    四维,可以降,但因为题目数据范围较小,不会超时,可以不降

    问题二:

    一行一行逐行逐格的考虑

    问题三:

    设dp[i][j][k][l]存放的是两个人同时分别走到i,j和k,l点时的最大路径和
    

    问题四:

    我们知道,两个同时走的人均需遵守只能向下或向右的规则,那么两个人的选择2 x 2就一共有四种可能,即

    1.都往下走

    2.一个往下,一个往右

    3.一个往右,一个往下

    4。都往右走

    那么状态转移方程为

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

    问题五:

    嗯,这个问题有点难考虑,初始值是什么?有特殊情况要考虑吗?如果两个人走到一个格子怎么办?如何实现第一个人走后格子数值置0

    一个一个问题来考虑,初始值?0 因为大部分空位都是0

    特殊情况?因为第0行和第0列已经被我们预先空出来且置0了,所以从检索第1行和第1列开始就不存在数组溢出的风险

    两个人走到一个格子怎么办?

    说实话,这个问题硬是把我难倒了,想了很久还是想不明白,本质上是对dp四维数组它代表的含义和本质没有了解透彻所导致的,在解决这个问题之前,我们先回归问题三和问题四。

    当我们用四重for循环遍历dp四维数组的时候,就是将i,j和k,l在这个棋盘所有的位置组合的情况列出,然后根据状态转移方程求出每一种情况的最大路径和,最后输出我们想要的右下角的结果

    当两个人走到同一个格子的时候,如果还采用问题四的方程,前面求最大值的式子是对的,但后面就不对了,问什么呢?我们看下题目,也是下一个问题

    如何实现第一个人走后格子数值置0

    也就是说一个格子的数只能取一次。那只需要走到相同格子时减去一个重复计算的格子数就好啦

    应该讲的比较详细了,可以试着自己写下代码,下面给AC代码参考

    AC代码:

    #include <bits/stdc++.h>
    using namespace std;
    
    int a[10][10];
    int dp[10][10][10][10];
    
    int main()
    {
    	int n;
    	cin >> n;
    	
    	//输入数据
    	int x,y,num;
    	while (1)
    	{
    		cin >> x >> y >> num;
    		if ( !x && !y && !num )
    			break;
    		a[x][y] = num;
    	}
    	
    	//四重循环
    	int i,j,k,l;
    	for ( i=1; i<=n; ++i )
    		for ( j=1; j<=n; ++j )
    			for ( k=1; k<=n; ++k )
    				for ( l=1; l<=n; ++l )
    				{
    					dp[i][j][k][l] = max ( max (max ( dp[i-1][j][k-1][l], dp[i-1][j][k][l-1] ), dp[i][j-1][k-1][l] ), dp[i][j-1][k][l-1] ) + a[i][j] + a[k][l];
    					//注意相同去重
    					if ( i==k && j== l )
    						dp[i][j][k][l] -= a[k][l];
    				}
    	cout << dp[n][n][n][n] << endl;
    
    }
    

    DP的优化之道

    写在前面:

    其实我在上面部分的例题中已经大概讲解了一些优化的方法(主要都是针对超时的优化),因为在谈及DP优化的时候,无非是从时间或空间的角度去优化。

    而效果最好的方法也是最难的方法就是降维了,把四维的想想看能不能通过相同点的归纳降到三维,那这样储存的空间就减少一个维度。空间就减少了,因为DP往往都需要借助递归/递推,那时间自然而然地也随着空间减少而减少了。

    但为什么说这个是最难的呢?因为降维以为着你能够找到高维重复相同的地方,并且你还要重新设计三维数组存放数据的意义,设计状态转移方程,也就是说你要重新根据套路五步法来一趟。况且不是所有人都能在刺激紧张的考试/比赛中面对所有DP题目面前想出降维的思路,毕竟绝大多数人都是一般人,那肯定就是一般的思路咯。

    当然,也可以单独的优化,如只优化时间或只优化空间,甚至可能出现牺牲时间优化空间,牺牲空间优化时间的做法,这取决你个人和题目的需要。(比如你的题目时间超时啦,但是空间还没有超过要求)

    因为篇幅原因和使用性的考虑,本文章着重讲解时间方面的考虑。这也是因为我个人在做题的时候,最长遇见的问题,或者说被迫要优化的原因就是因为超时啦!

    当然,还是推荐如果不是比赛/考试的时候自己多看看大神的优化代码,自己多尝试多种优化方向。

    时间的优化:

    其实讲到DP,在经过八道例题的洗礼后,最常见的方法就是递归和递推,然后大部分超时的原因都是递归的锅,因为递归能最快速的让计算机知道我们想让他做什么,解放了我们的思维量,只要列出DP状态转移方程后就可以直接摔给递归啦(但在一定程度上加重了计算机的计算量,这也是可能超时的原因所在),方便我们阅读理解和修改。

    这里我想再引用一下Leigh Caldwell在Stack Overflow上说的一句话:

    “如果使用循环,程序的性能可能会更高,如果使用递归,程序可能更容易理解,如何选择要看什么对你来说更重要。”

    如果你还不太理解递归,可以看我之前写过的一篇文章

    再次深入理解递归——总结设计易错点

    为什么会超时?

    也许正在学习练习递归的你并没有碰到递归超时的情况,那可能的原因是题目的测试数据太小啦!你的计算机计算能力还算可以,所以就不存在超时的问题。

    下面我以斐波那契数列举个例子让你理解下为什么会超时

    我们都知道斐波那契数列从第三项开始每一项为前两项的和,那么如果我们要求第七项,那么流程如下:
    在这里插入图片描述

    嗯,也许你已经发现了不对的地方,我们重复计算了5两遍,4三遍,3四遍…如果项数很大,重复计算的次数只会越来越多

    导致这样子的原因取决于递归的本质所决定的,我将此理解为触底才反弹。(下面会详细解释)

    如何优化?

    注意,我觉得这里要先特别区分一下递推和递归的区别,虽然只有一字之差,但意思和本质却截然相反。从小学数学的时候其实我们就已经接触了递推,就姑且还以斐波那切数列为例吧,我们只有知道了前面几项,比如1、2才能推第三项的值,只有知道了第三项和第四项的值才能推出第五项…以此类推递推到我们需要求的那个项,有点类似于滚大雪球吧,只能从小雪球滚起。

    而递归呢,方向就是相反的(但最后求解过程中又包括递推),先告诉你,我要求第100项的值,嗯,这时候你就说“只要我知道第98项和第99项我就能求出第100项”,紧接着“只要我知道第97和98项我就能求出第99项”…等等等等这样一直把大问题(求第100项的值)逐渐化解为小问题(第99、98、…、1项的值),从上往下递归,直到递归到最低,也就是第一项时停止,然后原路一层层的把数值返回,从第一项第二项求出第三项,返回求出第四项(这里不就是递推吗)所以我更倾向于把递归理解为反向索引+递推。

    总结来说递推就是自底向上,从下往上求解,而递归是从上往下,触底反弹,返回答案。

    嗯,可能你已经有点感悟了,其实在大部分情况下递归都能用递推来实现,甚至在某些情况下递推还要更好,因为递推是记忆化的,而递归要看你如何设计了,如果不是记忆化的递归,那么每次都要触底才能反弹,也未免太浪费时间了。是的,在有时候碰到数据很大的时候,用递归固然可以直接解放你的思维量,让代码看上去很简洁,也易于别人阅读和修改,但随之而来的可能是空间的极度浪费或者根本就不够用啊,这时候你就要用递推了

    我们还是以例题来说明吧

    跳台阶——超时、递归、斐波那契

    在这道题中,我们先看下我一开始写的递归代码:

    #include <stdio.h>
    
    int num( int n )
    {
        int total = 0;
        int i;
        if ( n==1 )
            return n;
        else
        {
            for ( i=2; i<=n; i++ )
            {
                total += num(i-1);
            }
            total++;
            return total;
        }
    }
    
    int main()
    {
        int t;
        scanf ( "%d", &t );
        while ( t-- )
        {
            int n;
            scanf ( "%d", &n );
            printf ( "%d\n",num(n) );
        }
        return 0;
    }
    

    推荐大家上机运行看看,当输入15、20等数据时几乎是秒出答案,但29、30时就要等上大概1秒的时间了,的确,刚刚上面已经给大家一个直观的理解了,重复计算的部分的确很多。

    那这道题如何改成递推呢?(或者记忆化递归呢?)

    先上代码:

    #include <bits/stdc++.h>
    using namespace std;
    
    int stair[31];
    
    int main()
    {
    	int t,n;
    	int i,j;
    	
    
    	cin >> t;
    	while ( t-- )
    	{
    		cin >> n;
    		stair[1] = 1;
    		stair[2] = 2;
    		for ( i=3; i<=n; i++ )
    		{
    			if ( stair[i] == 0 )
    			{
    				for ( j=i-1; j>0; j-- )
    				stair[i]+=stair[j];
    				stair[i]++;
    			}
    		} 
    				
    		cout << stair[n] << endl;
    	}
    	
    	return 0;
    
    }
    

    这个代码的思路就是将算好的数据储存在数组中,然后在大数据的时候直接调用,如果调用的时候还没算好就先算好再调用计算。这样子就相当于“记忆”下了递归的结果,不用每次都重新计算啦!

    大部分的递归优化都可以通过记忆化递归或递推实现~

    什么?你还是有点半蒙半懂的?没事,多自己练习优化就会啦,下面几个例子都是上面讲过的例题,就是自己用递归超时被WA,用递推就AC的例子,都有较详细的解说并附上了递归和递推的代码

    过河问题——动态规划的经典线性模型

    广工大2020级年ACM第一次月赛——Dio的面包工坊

    空间的优化:

    这里并不会做特别详细的讲解,只是大概点名一下思路而已,大家现在先回顾一下我们刚刚讲过的8道例题,嗯,它们是不是大部分都是一个区间一个区间和一行一行的储存dp数组数据呀,但是我们在计算并记录完一行或者一个区间的数据的时候我们大部分情况都是在被下一行和下一个区间利用完后就不需要了,或者说没有用了。这是由DP的无后效性的特点所决定的。但这也导致了闲置的数据空间,所以可以用滚动数组来减少这种情况。举个很惊悚的例子把(因为实在想不出其他例子了哈哈哈哈哈),假设你要走1000步,你可以左脚走完后右脚走,右脚走完后左脚走,这样轮回左右迈出步子后走完1000步,你也可以用1000只脚,每个脚走一步。

    降维的优化:

    在写在前面有说过啦,本文不详细讲,以后有空我会单独出一篇文章讲解的。


    写在后面:

    为了确保大家能够看懂这篇文章,我尽量每字每句都详细讲解,给出证明和解释,真心希望你能够在阅读此篇文章后从中多多少少有所收获。因此这篇文章我都投入了大量的时间和精力,前前后后不包括查阅资料的时间光是写文章的时间大概用了40多个小时,去举例,去说明,去分析,如果你觉得这篇文章写的还不错,点赞、关注和收藏一键三连就是对我最大的鼓励啦,我以后也会写更多更高质量的文章!也欢迎一起讨论指出文章可能存在的逻辑问题~

    在这里插入图片描述

    展开全文
  • 以下的讲解以这种时间的概念讲解(感觉更容易理解一些)。                 输入输出用例:第一行为事件个数,从第二行开始,每行为一个事件的开始时间和结束时间,中间用...

    题目:输入n个区间,给出每个区间的开始位置和结束位置(都是整数),求最多有多少个区间重叠?

           

    该题目也可描述为给出每件事情的开始时间和结束时间(都为整数),求最多有多少个事件同时发生?以下的讲解以这种时间的概念讲解(感觉更容易理解一些)。

           
           
    输入输出用例:第一行为事件个数,从第二行开始,每行为一个事件的开始时间和结束时间,中间用空格隔开。
    5
    1         4
    1         2
    2         3
    3         4
    3         5
           
           

    方法一:
            求最多有多少个事件同时发生,那我们可以依次把每个时刻(都是整数)发生了多少个事件求出来,找出最大值,即为答案。
            如图,先求出t1时刻发生了多少事件,再求t2时刻发生了多少事件,再求t3时刻发生了多少事件,一直求到t4时刻发生了多少事件。
            求某一时刻发生了多少事件,需要遍历所有事件,判断事件的起始时间start和结束时间end是否满足:start<=t<end,若满足,则t时刻发生的事件数+1。
           
            时间复杂度度警告!!!这种方法时间复杂度非常高,一共有tmax个时刻,每个时刻遍历一遍所有事件判断该事件在当前时刻是否发生,O(tmax*n)的复杂度。

    C++代码:

    int main() {
        // 处理输入输出
        int n;
        cin >> n;
        vector<vector<int>> vec(n,vector<int> (2));  // 保存每个事件的起始时间和结束时间
        int max_en = 0;       // 保存最大的时间
        for (int i = 0; i < n; ++i) {       
            scanf("%d%d", &vec[i][0], &vec[i][1]);      
            max_en = max(max_en, vec[i][1]);
        }
        // 求每一时刻发生了多少事件
        int res = 0;
        for (int i = 1; i <= max_en; ++i) {
            int cur = 0;    // 保存时刻i发生的事件数量
            for (const auto &j : vec) {
                if (i >= j[0] && i < j[1]) {
                    ++cur;      // 如果该事件的起始时间和结束时间包含该时刻i,则事件数+1
                }
            }
            res = max(res, cur);  // 更新某时刻发生事件数量的最大值
        }
        cout << res;
    }
    

           
           
    方法二:
            可以额外建一个长度为tmax的数组,数组的每个元素代表当前时刻发生的事件个数,数组元素全部初始化为0。然后只需要遍历一遍所有事件,每遍历到一个事件,就把数组的该事件的start到end部分元素值+1,表示这段时间又多了一个事件发生。最后数组元素的最大值,就是同时发生最多事件的数量。
           
            时间复杂度警告!!!这种方法时间复杂度仍为O(n*tmax),但每个事件并不是从0~tmax都有值,而是只占了一小段时间,因此最优复杂度低一点,比上一种方法快一点。

    C++代码:

    int main() {
        // 处理输入输出
        int n;
        cin >> n;
        vector<vector<int>> vec(n, vector<int>(2));  // 保存每个事件的起始时间和结束时间
        int max_en = 0;       // 保存最大的时间
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &vec[i][0], &vec[i][1]);
            max_en = max(max_en, vec[i][1]);
        }
        
        vector<int> v(max_en + 1, 0);   // 额外建一个数组,保存每一时刻发生了多少事件
        for (const auto &j : vec) {
            for (int i = j[0]; i < j[1]; ++i) {
                ++v[i];
            }
        }
        auto res = max_element(v.begin(), v.end());
        cout << *res;
    }
    

           
           

           

    方法三:
            以上两种方法都比较好理解,但时间复杂度太高,还有别的方法,以后更新。

    展开全文
  • 树状数组(区间修改+区间查询)

    今天,我们再在树状数组上进一步突破,我们来讲一讲区间修改和区间查询。同样的,这需要各位对树状数组的基本知识有所了解,大家可以看看我的另一篇文章:树状数组趣解
    下面进入正题。
    同样的,我还是先给代码,再讲解。其实,我个人比较喜欢直接看代码,有时,看别人的解释,反而看得稀里糊涂,不如先看看代码,自己会有自己的理解,然后再看解释就不会晕了。(也有可能是某些作者说得太简略了)

    代码

    有些是以前的代码,但由于会用到,这里可能会再写一遍。

    1、lowbit

    int lowbit(int x){
        return x&(-x);
    }

    2、单点修改

    void add(int *C,int x,int p){
        while(x<=n){
            C[x]+=p;
            x+=lowbit(x);
        }
    }

    3、前x项之和

    int sum(int *C,int x){
        int ans=0;
        while(x>0){
            ans+=C[x];
            x-=lowbit(x);
        }
        return ans;
    }

    4、求真正的前x项和(???)

    int truesum(int x){
        int sum1=x*sum(c1,x),sum2=sum(c2,x);
        return sum1-sum2;
    }

    5、区间查询

    int query(int l,int r){
        return truesum(r)-truesum(l-1);
    }

    6、区间修改

    void change(int l,int r,int p){//将[l,r]上每个数加上p
        add(c1,l,p);
        add(c1,r+1,-p);
        add(c2,l,(l-1)*p);
        add(c2,r+1,r*(-p));
    }

    在这些代码中,有些变量可能出现的比较突兀,我会在解释中说的。

    解释

    好,下面是cgg解密时刻!
    首先,我先讲一下总体的思路。
    我们设A[]是原数组。
    接下来我们需要引出一个概念:差分数组。你可能听过,也可能没听过,这都无所谓,我简单介绍一下:
    我们设差分数组是C[],那么有如下定义:

    1. C[1]=A[1]
    2. C[i]=A[i]-A[i-1]

    很好理解吧!
    那么我们下面要做一个公式推导。
    sum(1,n)
    =a[1]+a[2]+a[3]+…+a[n-1]+a[n]
    =c[1]+(c[1]+c[2])+…+(c[1]+c[2]+…+c[n])
    =n(c[1]+c[2]+…+c[n])-(0c[1]+1c[2]+2c[3]+…+(n-1)c[n]).
    这里sum表示前n项之和。
    那么我们有什么发现?
    我们可以设置两个树状数组,一个是c1[]表示差分数组,另一个c2[]则是c2[i]=(i-1)*c1[i]。这样的话,我们就可以区间查询了。
    那么我们又是怎么实现区间修改的呢?
    其实也很简单,我们看一下change()函数,有什么发现?
    我们会发现,它对于两个数组,每个只改了头尾两个值,为什么?
    这就要回到我们的定义,我们的两个树状数组均可以算的上是差分数组(c2也有差分的意味),所以,试想一下,如果我们对区间[l,r]上的每个数都加上p,那么c1[l+1]到c1[r]会发生变化吗?不会!因为区间内的每个数都加了p,所以他们之间的差是不变的,所以我们只需要改变两头的差值即可,这样就是实现了区间修改。
    再稍微辨析一下3和4两段代码,两个都是前几项和,但3求的是树状数组前几项和,而4才是原数组的前几项和,也是我们要求的。

    结束语

    这样的话,我们的树状数组估计一时半会不会再进阶了,希望各位能多温习,回头我会给大家找几道习题练手。
    剧透:接下来可能要讲线段树!

    展开全文
  • 为了便于说明,我们以数据结构中的字典类型举例,基于字典来讲解哈希和哈希表的概念与应用 文章目录 一、哈希和哈希表 二、哈希思想在信息领域的应用 三、哈希的设计和性质 四、常用的哈希函数 五、冲突消解技术 六...
  • 【实例讲解】贝叶斯推理原理

    千次阅读 多人点赞 2019-11-05 20:44:28
    今天看论文的时候,看到了贝叶斯推理,搜索的时候,正巧搜到了一个大牛的博客,博客中对于贝叶斯推理的进阶实例讲解,真的是非常精彩,这里将自己对贝叶斯推理的收获记录下来。如有理解错误的地方,欢迎指正共同讨论...
  • SVM通俗讲解

    2015-11-03 21:01:12
    很显然,第二部分是没有办法精确计算的,因此只能给出一个估计的区间,也使得整个误差只能计算上界,而无法计算准确的值(所以叫做泛化误差界,而不叫泛化误差)。 置信风险与两个量有关,一是样本数量,显然...
  • 线段树讲解

    2018-02-02 17:37:43
    线段树概念及说明 线段树(Segment Tree):线段树是一种二叉搜索树,其最擅长的是进行区间处理操作,通常树上的每个节点都维护一个区间,线段树树根维护的是整个区间。每个子节点维护的是其父节点所维护区间二等分...
  • 动态规划 区间dp

    2019-09-01 19:52:34
    概念 区间dp:在区间上进行动态规划,求解一段区间上的最优解。它是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。 区间dp是线性dp的扩展。 在分阶段地划分问题时,它与阶段中元素出现的顺序以及由...
  • 目录 1. 置信区间、置信限 2. 枢轴量法 3. 单个正态总体均值的区间估计 ...但这种判断的把握有多大,点估计本身并没有告诉人们,为弥补这种不足,提出区间估计的概念。 定义1 例题 定义2 单侧...
  • 划分树讲解

    2019-06-04 19:02:14
    划分树是专门用来求静态区间第k的一种数据结构 它主要利用快排的思想来进行建树和查询 比如给你一个长度为12序列{1,9,4,5,8,3,4,6,5,2,5,7} 我们要按照划分树来建树该怎么建呢 1.首先和快速排序一样,...
  • 线段树の一 区间

    2019-09-24 17:02:24
    一:线段树基本概念 1:概述 线段树,类似区间树,是一个完全二叉树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的...
  • 树状数组讲解

    2018-04-12 19:23:18
    树状数组1.... 树状数组主要有两个操作:数组元素的更新与某个区间内的查询 对普通数组进行一次修改或特定区间求和,时间复杂度为 O(N),N 为修改或求和需要扫描的数组区间大小。但树状数组则...
  • 区间DP解析超详细版!!...概念入门 价值与代价的组合嵌套成背包中状态,而区间DP,则是需要子区间的更迭,环环相扣由子区间之间的组合来组成父区间的值,通过级级解决区间的合并问题来得出最优值
  • 举例而言,自助样本通常用于评估统计估计量的方差或置信区间。根据定义,统计估计量是某些观测值的函数。因此,随机变量的方差是根据这些观测值计算得到的。为了评估这种估计量的方差,我们需要对从感兴趣分布中...
  • 小甜点,RecyclerView 之 ItemDecoration 讲解及高级特性实践毫无疑问,RecyclerView 是现在 Android 世界中最重要的系统组件之一,它的出现就是为了高效代替 ListView 和 GridView。当时它的出现解决了我一个大的...
  • HashMap原理讲解

    2016-05-08 10:50:18
    数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难; 链表 链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间...
  • 区间DP --算法竞赛专题解析(14)

    千次阅读 2020-05-16 20:16:58
    区间DP的概念、2种模板代码、经典例题、二维区间DP。
  • [转]LCT讲解

    2019-02-03 10:09:00
    区间求和 区间求最值 区间修改 求连续子段和 这个线段树就可以解决 具体做法不加累述了 (2)维护一个序列,支持下列操作: 区间求和 区间求最值 区间修改 求连续子段和 添加一段区间 删除一段区间 翻转一段区间 ...
  • SVM详细讲解

    万次阅读 多人点赞 2018-04-15 20:02:51
    后(称为松弛变量),就允许某些样本点的函数间隔小于1,即在最大间隔区间里面,或者函数间隔是负数,即样本点在对方的区域中。而放松限制条件后,我们需要重新调整目标函数,以对离群点进行处罚,目标函数后面加上...
  • 平衡树之splay讲解

    2016-12-20 19:52:33
     首先来说是splay是二叉搜索树,它可以说是线段树和SBT的综合,更可以解决一些二者解决不了的问题,splay几乎所有的操作都是由splay这一操作完成的,在介绍这一操作前我们先介绍几个概念和定义  二叉搜索树,即...
  • 线段树入门篇讲解

    2019-07-31 11:27:00
    总原理: 将[1,n]分解成若干特定的子区间(所开数组的大小不超过4*n,n是原数组...注意:区分3个概念:原数组下标,线段树中的下标和存储下标。 原数组下标,这里都默认下标从1开始(一般用a数组表示,a [1] , a[2...
  • 线段树讲解及例题

    千次阅读 2017-07-10 18:03:26
    线段树 转 一:线段树基本概念 ...线段树,类似区间树,是一个完全二叉树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操
  • 基础算法:差分讲解

    千次阅读 多人点赞 2019-03-09 20:37:51
    1.差分的基本概念: 如果有一数列 a[1],a[2],.…a[n] 且令 b[i]=a[i]-a[i-1],b[1]=a[1] 那么就有 a[i]=b[1]+b[2]+.…+b[i] =a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1] 此时b数组称作a数组的差分数组 换句话来说a...
  • MySQL基础讲解

    2016-09-08 11:06:41
    所以,现在我们使用关系型数据库管理系统来存储和管理的大数据量,所谓的关系型数据库,是建立在关系模型基础上的数据库,借助于集合代数等数学概念和方法来处理数据库中的数据。 RDBMS及关系数据
  • 1.统计量: 说到统计量说的一定是样本,是由样本构造的一个函数,例如我们常说的样本均值、样本方差等。 2.参数估计: 很多时候我们只能获取到样本的统计量,难以获得总体的参数,...区间估计 (1)点估计 用样本统计
  • 区间跨度的理解 上升趋势的区间跨度(下降趋势则相反) 上升趋势:高点至高点之间的K线根数,区间耦合存在,很少单独存在。 上升趋势的区间跨度:是指价格创出新高,到再次创出新高并收市于新高之上的周期,简称...
  • fhog特征讲解

    千次阅读 2018-03-05 20:44:14
    ND大神等人实验指出,将像素的梯度方向在0-180°区间内平均划分为9个bins,超过9个时不仅检测性能没有明显的提高反而增加了检测运算量, 每个cell内的像素为其所在的梯度方向直方图进行加权投票,加权的权值可以是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,503
精华内容 4,601
关键字:

区间的概念讲解