00:00
各位同学,我们把刚才讲的这些内容做一个小结,我们刚才讲了哪些内容啊,首先呢,我们讲了动态规划算法,对不对?把动态规划算法我们做一个小结,怎么说的呢?我们先来看一下。首先,在讲动态规划算法的时候,我们先给同学们举了一个实际的应用场景,就是最经典的背包问题,引起大家的思考。对不对,这是我们的一个应用场景,提出背包问题,背包问题具体来说呢,就是。这样子我把它放到这,放到这。就是有一个背包,背包里面有一个背包,背包呢有有它的容量,然后有些物品怎么放进去能够在满足。不呃,满足重量不超出,而且我们背包的总价最大。这是我们这背包问题的两个问题,也就是说两个要求,这就是我们所说的零一背包问题。
01:06
提出这个问题以后呢,我们就给同学们说一下动态规划算法,它是是一个什么样的算法,是不是在这呢?我们做了一个小结,呃,做了几点说明。给大家捋一捋何为动态规划算法呢?它的核心思想是把一个大的问题分解成小问题来解决。然后呢,它跟分支算法的区别在哪里,我们来看一下,与分支法不同的是。经过这个动态规划求解的问题。他们。就是他,他得到的子问题往往不是相互独立的。说的再直接一点,就是下一个子阶段的求解要建立在上一个子阶段的求解基础上。是不是我们在解决背包的问题时候,其实是有参考他上一次的装包策略是不是这样子的?
02:02
所以说动态规划呢,跟这个分制法它是有区别的。然后把动态规划算法说完了以后呢,我们就给大家直接来上这个代码了,也就是把这一个背包问题给大家进行一个实现。是不是就把这个代码给他。实现了一下,那在实现这个背包问题的时候,我们是怎么说的呢?我们先先把这个拿过来,我们是不是先做了思路分析。把这个整理一下啊,往这儿走一走。整理下我们的。这块。代码。我们先给同学们做了一个什么呢?做了它的思路分析,思路分析我们先说的是背包问题,它的一个分类。对吧。它的一个分类,什么分类呢。就是背包问题,有这种零一背包。
03:01
还有一种背包,叫完全背包。那我们这个地方是属于零一背包,所以说在分析思路的时候呢,我们是按零一背包来进行这个思路分析的。思路的分析是这样子给大家聊的,先给大家说了这个算法的主要思想是什么。是不是?也就是说我们指定了我们主要的一个事项,比如说v wivi,然后VIJ表示什么含义,在这里呢?通过一个动态规划的举例,就是按照这个举例,我们得出了一个公式,这个公式是我们这儿推出来的,是这样子的吧,那具体来说,其实我们是在这画的。是不是整体整体这个。分解分析的过程是在Excel表里面做的,然后呢,我们得出一个公式以后,这是我们得出的一个公式,得出公式以后呢,我们还做了一个验证,是不是这样子的,同学们好,那我首先呢,先把这个公式给大家拿过来。
04:05
它的结论在这里,我把公式先放一放,同学们不着急,好,这是我们推出的一个公式。那这个公式呢,主要是有这么三点吧。哪三点,我们来简单的回顾一下。第一点呢,就是V0等于V0节等于零。当wi wi大于节的时候呢,我们是直接取上一次的中包策略,当结大于等于wi的时候,我们要求一个最大值。对,然后针对这个地方,我们又画了一个图来给同学们聊这个画图,对这一个Excel图解。图解的一个分析,具体来说。就是这张图。我把这个放小一点,然后把整个图截过来好吧。放放小一点。这样就看得比较清晰。这样看着比较齐,往这边挪一挪。
05:01
大体来说就是这样一个分析的图解,我给大家拿过来。这边呢,我们还做了一个公式的验证,比如说VIJVI1。一它是怎么等于一千五的,还做了一个,就是这个值VI34为什么就等于。这个3500。是不是也做了一个分析,就是说相当于去验证了一下我们这边的几个公式是否正确。对吧,我因为我们刚提出这个公司的时候呢,你不敢保证他一定是正确的嘛,所以说我们做了这样一个分析。好,把这个分析做完了以后,是不是我们就代码给大家玩了一把。把代码就给大家实现了,这是相当于第七步了,对吧,我们叫做动态。叫做。动态。动态规划。归。规划什么呢?背包,背包问题的代码实现。
06:06
代码实现OK,那这块呢,我们也给他来一个标题三吧,这样比较简单一点,然后代码具体来说是哪一块呢?是不是这个。这一段就是我们背包问题的代码实现,我给大家放在一个表格里面去,同学们到时候可以去参考一下。好当我们把这一个。动态规划算法讲完了以后呢,我们就提出了KP算法。那怎么讲这个TP算法的呢?老规矩,我们首先提出了一个应用场景。KMP算法呢,它主要是用于对字串的一个匹配,所以说我们就提出了一个这样的问题,引起大家的思考,什么问题呢?就这样一个问题。对不对。OK。那提出这样一个问题过后呢,我们首先对这地方应该是。
07:00
刚才这样子好,刚才这样子给他来一个标号啊,把它分成两两块,提出这个问题以后,我们先用的是什么思想来解决的,我们是不是先尝试用暴力匹配算法,那暴力匹配算法呢,它比较简单,相对来说也比较好理解,但是呢效率比较低。所以说我们把这个暴力。暴力匹配思想的算法说了一下呢,我们走了一下代码,但是呢,我们也说了暴力匹配呢,一般来讲我们在开发中就不要去使用了,对不对?好把代码给大家写到这来。暴力匹配的代码实际上是在这个文档里边,我也拿过来。虽然他比较笨对吧,但也在你没有办法的时候,你用它也还是可以,只是效率比较低一点,对不对。好,这是暴力匹配,那暴力匹配算法说完了以后呢,我们就说,诶,那现在呢,就给他说一下KP,我们就把KP算法呢,做了一个说明,什么是TP算法。
08:03
在这里解个散。那这里我又提出了,说要彻底的理解KP算法,其实也是比较难的,对。那么我这里就推荐了一篇文章,对吧?如果同学们有兴趣,确实很想搞懂KP,它所有底层数理逻辑是怎么来的,包括数学公式什么推导出来的,包括有限状态机、无线状态机怎么来的,大家可以看这篇文章,但如果说大家只是站在理解KP算法的它的核心思想以及代码的实现上来说呢?其实我讲的就够了。是不是其实也就够了,那具体来说,我们怎么来分析这个KP的东西呢?好,我们。把这个说完了,我们就直接提出了这样一个问题来,我们把这个给大家捋一捋。我们就提出。一个实际的应用。就是字符串匹配。主板匹配呢,我们先提出的是。
09:00
问题。就是我们要解决的这个问题,那问题里面我们这有三个要求。要求一。啊,要求就是如果找到就返回第一次的位置,如果没有返回负一要求呢,用KP算法。对不对,然后呢,我们就做了思路的一个图解,最后是代码的实现,那思路的图解在哪里呢?各位同学,其实就在我们这个文档里边。是诶忘了啊,把它打开吧。是不是偏僻算法的思路分析实际上是在这个word文档,那我为了省事,我就一次性把它粘过来好吧,因为为了大家以后。比较好看,所以说我还放到我们这个笔记里面去,然后把图呢也带过来,带格式粘贴。好的,那这个整完了以后呢,我们就直接写代码,代码在哪里呢?代码其实就是在这里KP。A logm or algorithm algorithm,那这里面呢,我们核心的方法一个是next,一个是search,而hamp里面最核心的又是哪哪里两句话呢?一个是这句话,一个这句话,这两句话呢,是有点不太好理解的,对吧?就说你在进行遍利的时候,你要考虑相等的情况和不等的情况分别怎么去处理。
10:18
那这块呢,同学们可以把对照这个代码,然后去做一个做一个理解,应该也不是很难,好就是你把你如果站在代码层面上,其实也不是很难。然后呢,我把代码就给各位朋友放到我们的笔记中,其实你仔细想一想,代码其实挺简单。对不对,代码其实挺简单的,然后代码让你去写,面试官让你去写,我相信只要你认真去听了,应该没有什么太大问题。应该没有一个,不就是求一个next,然后一个search吗,是不是?就把这个好好理解一下就完事了。好,各位同学,那么这也就是我们讲的。前面讲的动态规划算法和KP算法的一个小结。
我来说两句