递归回溯算法流程图

今天讲解燕皇后问题，具体规则如下，一、在一个 ann 的棋盘上摆放皇后。二、每一行摆放一个皇后。三、皇后会攻击与他在同一行、同一列、同一斜线上的棋子。 四、所有皇后不能互相攻击。要求统计出所有的可行方案。例如，这是一套可行的方案，我们可以表示为零四七五二六幺三，数值代表的是摆放的列，所以则刚好可以表示摆放的行。 我们现在需要写一个程序，能够像这样输出所有的可行方案。对于八皇后问题来说，一共有九十二套方案。如果让我们动手尝试，过程可能是这样，先把皇后放在第一行第一个位置，然后寻找第二行的位置，前两个格子都不行，那就放在第三个位 位置。接下来尝试第三行。不行不行不行不行， 只能放在这里。按照这样的方法，一行一行尝试。假如遇到某一行全都不行的情况，那就回到上一行，将皇后移动到下一个格子，再继续尝试。一行一行地归尝试，如果不行，就回溯到上一行的下个位置继续尝试。 这个方法叫做回速法。接下来看一下程序的思路，每一行的尝试方法都一样，可以用地规算法实现。 将每一行已经放置的皇后位置存入列表，以便在放置皇后的过程中与列表中的每一项进行比较，判断是否在同一行、同一列或同一斜线。先看一下这部分代码，制作一个函数，类似是已经放 放过皇后的位置列表。若是当前测试的行，便是棋盘大小循环测试当前行的每一个格，将列表中当前行的纸设置为 i， 这里需要一个判断函数，判断是否可以放下棋子。建立一个判断函数需要两个参数，一个是已放棋子的列表，一个是当前行数。具体怎么判断，先留空，后面再讲解。如果可以放就递归到下一行， 如果放不了，就尝试下一个格子。既然是地规，就一定要有一个终止条件，如果当前行等于 end， 证明已经找到一套可行方案，显示出方案结束地规函数。接下来思考如何判断某个位置是否与已经摆放过的棋子冲突，是否在同一行。同一列很好判断， 主要是分析如何判断是否在同一条斜线上。这个问题可以这样想，在同一条斜线上的任意两个相邻的点，行差一，列也差一，也就是说同一条斜线上的任意两个点必然是行差呀，列差呀，其实就是行相减的绝对值等于列相减的绝对值。 最后来完善判断函数循环列表中的每一个值与当前行的值进行比较。如果值相等，也就是列相等或者值相减的绝对值等于行相减的绝对值， 返回 false， 如果都不冲突，返回 true。 最后我们来测试一下程序，设置棋盘大小为八乘八，创建一个长度为八的列表， 调用回溯法函数 测试成功。 但皇后问题代码不多，但不容易理解，下面是加了详细注视的代码，你也可以尝试修改验的值测试十皇后。二是皇后的情况，如果一时看不懂，就先收藏起来慢慢理解吧！

大家好，这里是代码算小路，我是程序员卡尔，这期视频呢，来给大家讲解代码算小路中回速算法章节的恩，皇后问题。 这道题目呢，确实是在回速算法章节里边比较难的题目啊，那他的提议是什么呢？给我们一个 n 乘 n 的一个棋盘，然后呢让我们在这个棋盘里面呢放 n 个皇后，那么放皇后的条件是什么呢？同一行里啊，不能出现两个皇后， 从一列里也不能出现两个皇后，然后四十五度，四十五度角也不能出现两个皇后啊，那满足这样的条件下呢，我们在 n 乘 n 的这个棋盘里边啊，放 n 个皇后，然后呢将所有的结果呢返回啊，这就是题目的一个要求， 那视力中呢，就是给我们一个四乘四的一个棋盘啊，那这样呢，我们大家可以看出来，我们可以放这四个啊皇后，对吧，这 这种放的方式也是可以的啊，那这道题目呢，为什么是在回速算法章节里边比较难的题目呢？啊啊，如果大家按照代码摄像录的顺序去刷的话，大家会发现我之前讲的啊，组合问题啊啊，分割问题啊，子极问题啊，排列问题， 我们所处理的呢，其实都是一个集合啊，一个集合，然后按照题目条件啊，然后再输出若干啊子集合，对吧？啊，那这里呢，给我们的是一个二维的数组， 那很多同学呢，大家都习惯了去处理一个一维的一个集合，对吧？啊，那一个二维的一个数组的话，大家就不知道哎，这让我应该怎么搜索就可能明知道这道题目呢？我们应该用回速算法去 去搜啊，但是呢，也不知道这个回速算法如何去搜这个二维的这个棋盘，对吧？啊，那这 这个呢，就是这道题目的一个难点所在啊，那首先呢，我们先想一下，如果这是给我们一个棋盘，我们暴力啊，想要暴力把所有的啊皇后的位置都没举出来，我们应该怎么做呀？ 啊？我们是不是如果这是一个四乘四的一个棋盘的话，我们是不是要嵌套四个负循环呢？第一个负循环便利第一行，对吧？里边嵌套个负循环便利第二行，里边再嵌套个负循环便利第三行，里边再嵌套个负循环便利第四行。 然后呢，每一行呢，是每一局这对应行的这个位置往后分别放皇后，然后我们再去检查，哎，这个位置放皇后可不可以，对吧？非常一个直白的，我们就用附嵌套附循环的方式，应该就这么写啊， 那这是四乘四的棋盘，那五乘五呢？六乘六呢？切成七呢？啊，你就会发现你的后循环欠套不下去了，对吧？啊，所以说呢，我们 我们就用回速算法来解决这道题目，那回速算法他能给我们带来哪些便利呢？啊？首先回速算法他也是暴力搜索，和我们刚刚讲的这种负循环嵌套的方式呢，其实实验法度是一样的啊，但是回速算法呢，就是帮我们用地规的方式啊， 去控制我们嵌套负循环的层数，对吧？啊，如果这是一个四乘四的，我们就递归四层啊，然后呢，每一层递归里边有一个负循环啊，去啊，便利每一层所对应的位置，对吧？啊，如果你是五乘五呢，我们就递归五层啊，六乘六呢，我们就递归六层啊， n 乘 n 我们就地规 n 层啊，所以说呢，我们就每一层地规去控制一个负循环，对吧？啊，就相当于是通过地规的方式来控制这个嵌套负循环的层次。那么大家了解了如何用回速算法去解 这个？恩，皇后问题之后呢，我们再来看一下他的树形结构是什么样的啊？因为画棋盘会比较麻烦，那么我就事先把这个树形结构呢给大家画出来了啊，我直接来讲解啊， 那么我们这里呢，举例是一个三乘三的一个棋盘啊，三乘三的一个棋盘呢？我们第一层地规里边啊，我们应该是取哪一行啊？我们第一层地规里边是不是取第一行啊？第一行里边你取一、取二、取三，分别取的是哪一个位置？就是第一行里边 一的位置，第一行里边二的位置，第一行里边三的位置啊，也就是说你第一层地规里边分别取的数，你对应的就是第一行，对吧？啊？那这里呢，我取了第一行之后呢，下一层地规取的是哪一行啊？下一层地规我是不是就要取第二行了呀？第二行你取一、取二、取三， 三的话，那分别是第二行里边这里啊，我们把皇后放在第一个位置，第二个位置，第三个位置，对吧？那大家可以发现放这里可不可以啊？不可以，是不是列里边重复来啊？放这可不可以啊？不可以， 是不是这个四十五度角重复了呀？对吧？啊？那放这里可以对吧？啊，当然在这里边还有分支，我就不全画了啊，因为这个竖音结构还是挺大的啊， 那这边取三的话呢，我们接下来再下一层地规，那便利是第几行啊？是不是第三行啊？对吧？啊？第三行，那第三行取一、取二、取三，分别放的位置就是这里，对吧？啊？那放这里可不可以啊？ 这个裂是不是重复了呀？放这里可不可以啊？四十五度角是不是重复了呀？放这里可不可以啊？裂是不是又重复了呀？哎，那大家可以发现，哎，好像这个三乘三的这 棋盘好像就没有一个合法的一个，呃，放皇后的位置，对吧？啊？其实三乘三的，恩，皇后问题本来就是无解的啊，就是没有放皇后的位置啊， 那么画一个三乘三的就是为了这个竖行结构相对来说好画一些，那么通过这个竖行结构呢，就帮助大家进一步明确我们回速算法是如何搜索的呀？ 我们这里每一层里边啊，每一层里边我们都是取一、取二、取三，但是我们每层地规里边对应的是不同的行，对吧？我们最开始是第一行，然后是第二行， 然后是第三，这样呢，我们就通过地规的方式啊，来把这个棋盘里边每一行的位置是否应该放黄后都给便利到了，对吧？那么我们这个树形结构的深度是什么呀？是不是就是我们这个棋盘 n 乘 n， 那么我们这个树的深 度是不是就是 n 呐？我们这个数的宽度是多少啊？我们是不是每一行里边取每一个数啊？那就是我们这个 n 乘 n， 你每一行的长度就是我们这个数的宽度，对吧？啊？ 那如果大家呢，能把这个竖行结构画出来的话呢？相信啊，用回速算法来解决这道题目呢，其实就简单不少了啊。那接下来呢， 我们再来看一下具体的代码应该怎么写。首先呢，我们定一个全局变量啊，来去收集我们符合条件的所有的棋盘情况啊。那么这个 redot 呢，其实是一个三维数组啊，三维数组， 因为我们每个棋盘其实是个二位数组啊，然后我们这是不是要放若干棋盘啊，所以说它是一个三位数组啊，那接下来呢，我们是低归函数的参数和返回值 by the twenty 啊，我们应该传授 什么参数啊？首先我们传入是棋盘是吧？ charles old 啊，然后呢，我们要传入这个棋盘的大小啊，其实不传入棋盘大小也可以通过它来去取棋盘的大小啊，但是还是传入进来吧，每次啊，边界控制的时候方便一点啊。 然后呢，我们还要传入一个肉，这个肉是来做什么的啊？其实就是行，是吧？我们每一层地规是不是第一层地规是不是第一行啊？第二层地规是不是第二行啊？第三层地规是不是第三行？那么我们怎么知道是第几行啊？是不是通过肉来记录一下呀？啊？ 那么接下来呢，我们是不是要看终止条件呢？我们最终得到的棋盘情况是不是在叶子节点下呀？那么我们的结果是不是就是在我们的终止条件来去收获我们的结果呀？对吧，我们终 条件是什么呀？我们肉是控制我们的第几行，对吧？啊？那么如果我们当前便利到第三行了，也就是说当我们的肉等于，等于什么呀？等于等于 n， 也就是说我们这是一个 n 乘 n 的一个棋盘，然后当我们便利到第 n 行了，说明什么呀？我们是不是到叶子节点了？那么到叶子节点是不是就到我们收获结果的时候了啊？那我们是不是要把我们的 result， 把我们的棋盘，此时的棋盘放进我们的接轨机里啊？对吧？ 然后呢？ reten 这里呢？有同学可能想，哎，你到叶子接点，他不一定是合法的呀，对吧？你怎么都放进我们的这个 结果激励了啊？其实呢，在下面的时候呢，我们进入地规的时候呢，会对合法性进行一个判断，也就说这里取一的时候，我们直接就不会再往下去地规了，所以说这种情况压根他就不会走道，对吧？啊， 所以说，如果他走到叶子节点了啊，那就一定是合法的一个棋盘，就是放皇后之后的合法的一个棋盘，那么我们就将这个结果呢，放进我们的结果棋啊， 那接下来呢，就是我们取数的过程，是吧？我们这里啊，假如在这层地规里面，我们取一、取二、取三，那这个逻辑在代码里对应的是什么呀？是不是我们的腹部循环引得 i 等于零 哎？小于什么呀？ n 是吧？我们这个宽度 n， 然后，哎，加加，那么在这里我们是不是就开始取数了呀？那这里我们取一、取二，取三， 取一的话，我们取一之后，我们是不是要判断一下，第一行第一个位置放皇后这个棋盘是不是一个合法的棋盘，对吧？如果是合法的棋盘我们才放吧，对吧？所以说呢，我们要判断一下你这个位置是不是一个合法的，那当前我们是第几行啊？ 啊？当前第几行？是不是这个是五行？那么这里呢，我们最开始调用这个函数的时候，传进来的是不是零啊？啊？因为我们最开始是第零行吗？对吧？啊？第零行啊， 那当前呢，我们是不是第肉行啊？然后是第几个位置啊？是不是？哎呀哎，其实就是列，对吧？肉其实就是行啊，然后呢，就是这个位置，此时我们锁定这个位置了，然后呢将棋盘传进来，对吧？啊？ 呃，首先这里边我们要有一个函数啊， if is valid 啊，这一个函数啊，我们去判断这个位置是否合法啊，然后呢 chase or 然后将这个棋盘大小传进来啊，这样啊， it's valid 呢？就来判断一下你这个 第入行啊，第挨个位置这个位置放行后，在这个棋盘下这个棋盘的大小下他是否合法，那么这个函数如何实现呢？ 其实这个函数就是判断一下行里边有没有重复出现皇后，列里边有没有重复出现皇后，四十五度角有没有重复出现皇后啊？ 那这个函数呢，我在白板上就不写了，那大家可以去代码所有的网站上回速算法章节本期视频的文字讲解版呢，去看一下这个函数的实现啊，那这个实现这个函数的思路还是很简单的啊，那大 家看一下就会明白了啊，那白板上呢，我就写关键性的代码啊，那同时呢，本期视频的文字讲解版呢，也有其他语言的时间版本啊，那大家呢，都可以去看一下，那么这里呢，我对这个位置放皇后，如果是合法的话，我是不是接下来这个位置就可以放皇后了呀？那这个位置 chase 哦，它的位置是什么呀？肉，然后，哎，对吧？是不是可以放皇后了？放一个 q， 对吧？啊？那这个位置啊，放了皇后之后啊， 呃，例如说这里啊，我们在这个位置放了皇后之后，此时我们是不是进入下一层地规了呀？我们是不是进入下层地规？下层地规是什么呀？然后 将棋盘传进来，对吧？然后棋盘大小肉传进来，什么？是不是肉加一啊？对吧？这里为什么要肉加一啊？ 我们这里便利的是第一行，下一层地规，我们是不是便利第二行啊？再下一层地规，我们是不便利第三行啊，所以说肉是来控制我们本层地规里边， 你便利的是棋盘里边的第几行，对吧？所以说你便利到最后一行的时候，若等于等于按的时候，我们就是到叶子结点下了，对吧？就是我们收获结果的地方了，对吧？啊？那我们接下来是不是回速啊？ 拆死包的肉，哎，等于等于什么呀？是不是给他给他再回速过来啊，对吧？啊？为什么要 有回速啊？为什么要有回速啊？我们这里啊，这里取一之后，取一之后，这里放皇后，接下来是不是要把它啊去掉，然后回速过来，再取二，然后这里变成 q 啊，对吧？啊， 所以说呢，我们要有一个回宿的过程，如果你要不回宿的话，整个棋盘全让我们塞满了皇后，对吧？所以说呢，正是因为有回宿，你这里取一了，然后呢才能把这个一的位置呢又变回啊，默认位置，然后再回来这里呢再取二，这就是一个回宿的一个过。 那么我在讲呃，回速算法章节里边每道题目涉及到回速的时候呢，我都会给大家举一个例子啊，那么此时呢，恩皇后这道题目的代码其实我们就写完了啊，大家是不是发现哎，这个传说中的恩皇后是很难的题目啊，怎么代码这么简 简单呢对吧啊，其实恩皇后的代码就是这么简单啊，如果大家能思考到了我们如何使用回速算法啊，去便利这个二维数组啊，如何去便利啊？其实我们是用地规呢来控制每一行，然后呢我们每层地规里呢是 建立每一行里边的每一个情况，一二三啊每一个情况啊，那如果想到这一点呢，我们如何去这个搜索啊，二维矩阵啊这种搜索方式的话，其实恩皇后问题呢，其实就是一道很简单的一个问题啊， 那这里呢就是 x y 类的这个实线呢，其实也不难啊，就是判断一下同行里边别有啊，重复的，同列里边别有重复的四十五度角别有重复的对吧？那么很多同学呢，会感觉恩皇后很难就没有思路，是因为大家呢都习惯去处理一尾数组是吧？啊？那组合问题啊， 子级问题啊啊排列问题啊，对吧啊那分割问题对吧啊？都是处理一个一位数组啊，那么二位数组啊，只要我们按照这个啊树形结构，我们每一层地规里边处理每一行每一层地规里边处理每一行，那想到这一点的话，这个代码就很容易写出来。 那好了，那本期视频呢？我们就讲解到这里了，这里是代码孙小璐，我是成员卡尔，感谢大家的三连支持。

大家好，这里是代码孙小璐，我是程序员卡尔。最近呢，在公众号里，我已经开始讲解了回速算法， 那么说到回速算法呢，刚开始学这个算法的同学，其实呢都很难受啊，真的很难受，因为呢，回速算法很抽象 啊，如果之前没有接触过这种类似的算法的话，刚开始学啊回溯如何去搜索，真的是很难啊 啊，所以呢，呃，我在公众号里呢，在讲回速算法的时候呢，也发现啊，大家在学习回速算法的时候呢，呃，都是有很多问题，所以说呢，我会出一个啊回速算法的系列视频啊，来将回速 算法呢啊，从他的理论基础到他实际解决的问题呢，来做一个详细的介绍。那这一期视频呢，我先来对回速算法做一个整体性的概述啊，这样呢，大家对回速算法有一个整体性的了解 啊，之后呢，我还会出一系列就是回速算法所解决的问题，这样呢，大家就会理解的更深刻一些了，那么那么我们开始讲解回速算法，说到回速呢， 说到回速呢，就要知道地规啊，那回速和地规是相辅相成的，只要有地规就会有回速，那么回速它隐藏在哪里呢？通常都是地规函数的下面， d 规函数的下面的部分就是回速的逻辑 啊，这里通常呢，那有的同学可能会问，哎，我为什么要回速呢？我不回速可不可以这个问题呢？在下面的讲解中啊，同学们自然就会明白了，为什么下面一定要做回速的操作， 包括之前啊，在公众号里已经讲了二叉数的系列，那二叉数他在递规的过程中都会有回速的操作，只不过是有的题目用到了回速，有的题目他没有用回速。 那么说到什么是回速算法之后，我们知道啊，地规和回速是相辅相成的，那地规函数的下面就是我们回速 的过程啊，通常呢说回速函数啊，其实呢也就是指地规函数，因为没有就是完全的是一个回速，用来回速的函数，其实呢都是指地规函数。那么说完回速呢，我们再来说一下回速啊，回速搜索法，它的效率， 回速法它其实是一个纯暴力的搜索， 他并不是什么一个高效的一个算法，就是纯暴力啊。嗯， 那有同学问了啊，为什么啊，这么一个纯暴力的一个搜索算法啊，效率这么低，还要用回速法呢？因为有些问题能 暴力搜出来就已经很不错了，由负循环去一层一层嵌套的话，根本都搜不出来。所以说呢，要依靠啊回速法才能把所有的结果呢搜出来。 那接下来同学们指定好奇了，那什么问题这么牛逼，我用暴力都实现不了，一定要用回速法来解决呢？那么我们来看一下回速法他都能解决哪些问题。首先呢是组合问题， 组合问题呢，一般就是给你一个集合，一二三四，然后在这个集合里啊，找出啊，大小为二的组合啊，那他的组合都有多少呢？有一二，有 一二，有一三，有一四，有二三，有二四，有三三，有啊，有三三四，对，这里是三四， 那么大小为二的组合有这些，那找出它的这些组合就是一个组合问题，那接下来呢，回速算法还能解决切割问题， 切割问题呢，通常都是给一个字符串，问他有几种切割的方式， 或者说呢，再加一些特定的条件，给你一个字符串，如何切割才能保证他的子串都是回纹子串，问有几种切割方式啊？这样呢，都是可以统称为 是一个切割问题，然后呢就是子极问题， 什么是子级问题呢？还拿这个一二三四来举例， 一是这个集合的紫吉，二也是紫吉，三也是紫吉，四也是紫吉，一二是紫吉，一三是紫吉，一四是紫吉， 然后二三是子吉，二四是子吉，三四也是子吉，一二三也是子吉，一二四也是子吉，等等啊，就是把他的子吉都列出来，就是他的子 急问题，那这种方式呢，大家也可以想一下，哎，我用负循环去嵌套，如何能把他们的这个子急能求出来呢？其实还是很困难的。然后回速算法还可以解决排列问题， 同学们应该经常能听到排列组合，排列组合，究竟什么是排列，什么是组合呢？ 针对组合的话，例如说一二一三一四组合是强调没有顺序的，也就是说 如果整个这个集合是一二的话，问他有几种组合，他只有一种组合就是一二，那如果这个集合是一二，求他的排列，那他有两种 排列，一个是一二，一个是二一。这样大家就可以看出来了，排列是强调元素的顺序，而组合不强调元素的顺序，所以说这就是排列和组合的差别。 然后回速算法呢，还可以解决棋盘问题， 棋盘问题呢，都有哪些呢？首先就是恩皇后啊，恩皇后和解数独这些呢都是棋盘问题， 那如果啊，同学们不了解什么是恩皇后，什么是解数读，可以自行百度一下，其实呢都是一个很复杂的棋盘问题。那同学们现在呢，就说可以了解啊，回速法他都 都能解决这些问题，那这些问题呢，用我们传统的这种啊暴力搜索方式啊，就是用我们的复活循环圈套，一层一层的圈套，其实呢是不好解决的，也写不出来这种代码啊， 必须要用回速搜索法啊，也就是回速法来解决，那这个回速搜索法就是一种纯暴力，纯暴力把啊组合如何组合，如何切割， 找到他的子级，找到他的排列集合，找到他的所有的棋盘情况，就是一种暴力的搜索方式。 那我们了解了回速法可以解决这些问题，我们再来看一下如何理解回速法，因为同学们在接触回速法的时候呢，嗯，都会发现其实他是特别的 抽象的，如果想要清晰的了解回速法的话呢，最好是把回速法呢抽象成一个图形结构啊，这种图形结构呢，会有助于我们的理解，也有助于我们用这种思维方式去解决这些问题。 要不然去解决这些问题时候，靠脑动模拟回速的搜索过程，其实是特别困难的，容易绕着绕着就给自己绕进去了。那么我们来看一下如何理解回速法， 回速法呢，都可以抽象为一个竖行结构，对，是所有的回速法针对于这些问题所对应的解决方式都可以抽象为一个 树形结构。为什么回溯法可以抽象为一个树形结构呢？首先我们说了，回溯就是一个地规的过程，那么地规他就一定是有终止的，我们来看一下这棵树啊， 回速法呢，通常都可以抽象为一个 n 叉数， 一般来说这棵树的 宽度啊，这棵树的宽度呢，就是我们在回溯法中呢处理的这个集合的大小啊，也就是每个节点所处理的集合的大小啊，这里通常我们是用负循环来进 便利了。那这棵树的深度呢，就是这个地规的深度啊，因为地规它一定是有中指的，中指的都有一层一层的向上返回，通常呢这个重方向就是地规来处理的 所有的啊，回速算法解决的我刚才说的所有的这些问题都可以抽象为这种结构， 那后面呢，我在讲解具体的问题的时候呢，都会把这些问题抽象为对应的树形结构来进行讲解，这样呢大家就会理解的更容易一些。那么我们说完如何理解回速法的话，我们再来介绍一下回速法的模板， 一般来说呢，回速法的回速法七十，一般来说呢，回速法呢都是它的地规函数呢，都是没有返回值的，就是一个 y 的 void， 那么这个 d v 函数呢，一般起名叫 back tricking， 当然了大家可以有自己的习惯啊，但是一般业界啊，统一的起名方式都叫 back tricking， 然后就是他的参数，回速法的参数呢，一般 情况下是比较多的啊，所以说不太容易，在一开始的时候呢，就能把他的所有参数都确定下来，但是这也没有关系，我们在写逻辑的时候呢，遇到了，哎， 想用什么数据了之后我们再在这里添加参数就可以了。接着我们就要进行一个终止条件，因为地规一定是要有终止的。 if 终止终止条件 在到中指条件的时候呢，一般情况下来说就到我们收集结果的时候了。在这个树形结构中，对于一般问题，例如说 组合问题，例如说切割问题哈，例如说排列问题和呃，部分棋盘问题，都是在叶子结点，就是我们收集结果的时候，只有子集，问题是在啊，每一个节点都要去收集结果啊。说到这里大 大家可能有点不理解，但没有没有关系啊，我在讲解具体问题的时候呢，都会把这个内容再会，呃，再会详细的讲一遍 中指条件，然后我们就要收集结果，通常都是在这个叶子节点的时候呢，就要收集结果了。 那同学问了，哎，我收集什么结果呢？例如说这个组合问题啊，那我们刚才求的这个组合一二求组合一三 这些一二一三就存在于叶子结点上，我们通常在这里面就要把一二一三这些啊，一二一三啊这些组合呢放进我们的一个结果集里， 那收集完结果之后我们就要 return 了，不要忘记 return， 那么我们处呃，那么我们处理完终止条件了之后呢，就进入了一个单层搜索的逻辑。单层搜索的逻辑一般情况下是什么样的？ 一般情况下呢，是一个负循环， 一个负循环，这个负循环呢？负循环，这个负循环的参数呢是用来处理啊这个集合里的每一个元素，通常这里呢放的是集合的元素，及 也就是说这个负循环的便利的 就是集合里的每一个元素，那其实也可以对应的是这个节点的所有的子节点的个数，通常在这里呢是处理节点。 哎，那有同学问，这是处理节点，是处理什么节点呢？那我们再再拿这个举例，那这个一二三，我们在收集他的子级一二的时候呢，这一二是怎么来的啊？是吧？那我们在这收集结果的时候，就把一 二啊放进我们结果集了，那这个一二是怎么来的呢？就是在这里处理节点的时候，把这个一二啊就是放到了一个数组里，然后以至于在中指条件里面 啊，这里收集结果的时候，才会把一二放进我们的结果集里。那处理节点下面呢就是地规 下面，这里就是地规函数，这里呢就开始进入我们的地规的过程了，那也就是在这个树形树形图里边这一层一层的往下走，那地规下面就是我们的回速操作， 回速操作呢，其实就是撤销啊，这个处理节点的情况。哎，那我们好不容易处理了节点，为什么还要撤销呢？我们还拿这个来举例，这个集合啊，一二三里边我们求他的 组合，假如我们一开始呢是放进来一了，后来呢放进来二，那么这个二呢，就是我们要的一个 呃，组合了，是吧？那么我们是不是要把这个二呢再做回速的操作，把这二呢再弹出去重新变成一，然后再把三加进来，这样我们才能得到了一个一三的组合呀， 一样的道理，我们还要把这个三回宿撤销掉，完了之后再把四加进来，所以才会得到一个一四的组合， 如果没有回速的操作的话，那么我们在处理这里就会一二三四一直加下去啊，就没有一个撤销的过程，这样我们就不会把所有的 组合情况呢都求出来了，所以说这就是为什么我们要有回速的操作，在这处理完之后呢，在下面结束我们的负循环，接下最后呢就是一个呃一个正常的一个 retin 的操作了啊，整体上， 整体上呢，这个就是啊回速，这个呢就是回速算法的一个 呃一个模板。那大家呢，想要呃得到这个模板的具体的代码的话呢，可以在公众号代码随小鹿后台回复 回速法理论基础啊，就可以得到这一期视频的啊，一个文字版啊，然后还有以及这个模板的具体的一个北代码啊，其实我这边 写的呢，还是会经典了一点，那大家可以在这个具体的文章中啊，看到这个整体的这个模板，那这个模板呢，如果啊做过回速法相关题目的同学就会看着非常眼熟， 因为会发现，哎，我们所做的所有的回速法的题目都离不开这个模板， 可以说就是按照这个模板照葫芦画瓢就把这些问题呢给处理了。当然说这么说有一点夸张，每一种问题都有自己的特点，但是最终写出来的代码都离不开这个模板的风格。 好了，那我就介绍到这里了，那大家想看视频的文字版呢，刚才已经说了，可以 在公众号啊代码孙小璐后台回复回速法理论基础就可以得到这期视频的文字版，以及啊我的回速法的模板代码。 嗯，那么我们这期视频呢，就讲到这里了，可能之前没有接触过回速法的同学呢，看这个视频感觉就是有一种懵懵懂懂的感觉，感觉说到哪都呃，不是那么很明白 啊，这个呢，这个呢，很正常，因为回速法他确实就是比较抽象，后面我们再用 啊，本期视频所讲解的理论知识来处理具体问题的时候呢，同学们就会知道了啊，这期视频讲的每一个点，在处理相应的问题的时候呢，都能用到 上，而且非常实用。好了，那我们就分享到这里了，感谢小伙伴们的观看。

接下来啊，想给你介绍一个什么回宿与什么与地推的概念。那我们通过一个例子，比如说啊，现在有四个人啊， 四个人坐在，坐在你面前啊，怎么办呢？你问呢？你问第四个人的薪水是多少，他怎么办呢？他不跟你说，他说啊，他比第三个人多一千块钱，那怎么办？你是不是得问第三个人？第三个人他也不说，他说我比第二个人多一千块钱，你怎么办？你是不是得去问第二个人，第二个人怎么办呢？他也比较皮，他怎么办呢？他说啊，我比第一个人多一千， 那你怎么办？你就不得不怎么办，于是就不得不问第一个人。然后啊，这第一个人比较靠谱啊，比较诚实，他就直接告诉你了，说我每个月五千。那我现在问你了，第四个人是有多少？那 这个问题的思路什么呢？要知道第四个人的月薪就必须知道第三个人的，知道第三个人的就必须知道第二个人的。想知道第二个人的就必须知道第一个人的，对吧？并且每一个员工都比前一个多一千块钱，那数学表达是什么？数学表达 就这样，第四个人呢？是第三个人呢，加一千块钱，第三个人呢？是第二个人加一千块钱，第二个人呢？是第一个人加一千块钱，然后第一个人的月薪是五千，对不对啊？那总结出来的规律是什么？总结归来的规律就是塞了个 n 等于什么啊？塞了个 n 减一加一千块钱吗？对不对啊？那塞了个一又怎么办？又等于五千，但恩，等于一的时候， 对不对？那这很明显，这是一个什么呢？这是一个地规啊，这是一个什么呢？这是一个回宿于地推的过程啊。那什么叫回宿的过程呢？一次层往下找答案，你要求三六一四，你就必须去求三六一三，求三六一，必须求三六一二，求三六一二，必须求三六一，这是一个回数的过程， 当你得到最终答案的时候怎么办？你是不是拿着这个答案怎么办？你是不是要往回推？什么？是不是推结果？那这个一层层往上推的过程就是呢？叫地推的过程啊，一个叫回数，一个叫地推，那这就是这两个概念，回数就是一层层往下问，地推就是一层层往上推啊，然后啊，代码实现的话也很简单，就是 c 六于 n， 然后呢？一负 n 等于什么？ n 等于一怎么办？是不是直接返回五千？否则怎么办？是不是返回一个 cl 与 n 减一加一千块钱，这个就是一个什么呢？这就是一个 dj 的过程， 对吧？函数怎么办？这是个赛路月加号号，这是不是也是赛路月加号号？是不是自己掉自己？但是呢，每一次在掉的时候怎么办？这个 n 数相当于数量就会下减了，但 n 减到一之后还会掉吗？不会掉了，是不是直接返回五千了，对不对啊？那你这样的 s 等于什么？ c 六于四怎么办？普云的 s， 这个什么八千啊，结果就是八千。 那这里还有个例子啊，说地规的本质啊，就是在做重复的事情，所以理论上地规可以解决的问题，循环也都可以解决，只不过在某些情况下，使用地规会更加容易。比如说一个签到多层的列表要求打印出所有的元素， 那你在写的时候你可以怎么办？比如说这么一个列表要求你打印所有的元素，那你怎么办呢？你就可以 fr ex， 然后呢 e fex exx 判断某个东西是不是属于列表，如果他是列表怎么办？你是不应 打印？你是不是再让他继续走这个函数，再判断他是不是列表？如果他不是个列表怎么办？是不是把这个结果打印出来？那这样的话你会发现你用几行代码就已经能够实现了。看似比较复杂的问题，你会发现打印的结果是什么呢？就会将列表里面的某一个元素都打印出来，无论是列表，他列表还是说就是单单的一个元素 啊，这个是你在用地规函数的时候的一个什么，一个简便的一个地方。

这一题我们来看一看，就是电话号码的这个字母组合，呃，这个是什么意思呢？他是说啊，就是有一个这个电话号码啊，就是其实就是我们的这个手机的键盘啊， 那呢？二到九嘞，他可以表示他所有的字母，就是比如说那二，那他就有 abc， 对不对？好，他就希望就说你按了，比如说二三啊，那么他的所有的这个字母的组合，那其实就什么？就是比如说 a 啊，你加了三，对吧？那是 ad， 对吧？有可能啊， a 一也有可能， af 也有可能，对吧？然后呢？ bd 啊， be 啊， bf， 那么都有可能，对不对啊？所以的话，其实就是这样子的啊？好，那既然是这样子的话，那么我们怎么去操作呢？其实啊， 那么在这里的话，我们可以看到有一个规律啊，其实其实也就说我们啊，比如说我们要说其实就是什么做一个什么便利的这样子的一个操作，对不对？好，然后呢这个便利的操作的话，其实我们可以总结一下，就是说他会有一，就是我们可以封装成什么样的一个函数，就说每一次啊，每一次什么， 就是说跟什么下一次这个什么所有的这个情况拼接，对不对啊？比如说当前，哎，我这个 a， 那么我就要跟什么，比如说这个三啊，他什么进行所有情况的一个什么拼接，对吧？比如说把 ad 啊 d 加在 a 的后面，对吧？啊？ e 加在什么我的这个 a 的后面，然后 f 加在 a 的后面，对吧？ 那这里的话，当然我们第一次他什么他有这个 b 系，他还有 b 系嘛，对吧？那也是嘛，把 d 加到 b 的后面，加 c 加后面，那这样的话形成的一个什么数组， 然后最终我们把这样子的一个数组返回出去就可以了，对不对？是不是这样子？那所以的话按照这样子一个形式啊，那么我们可以这样去写，那首先的话，我们啊就是要有一个映射，嗯， 一般呢，在装饰柜里面的话，我们可以映射的话，用这个 map 对象，或者是说我们直接用什么用一个对象来进行定义，对吧？好， ok， 那比如说我们啊二 这个东西呢，它就里面就什么，呃，这个这个属性里面啊，就有这个 abc 啊，这三个字，对吧？啊， ok， 那就 ab、 c 三个字，好，然后的话我们的这个三，对吧，那么就会有这个 now， d， e， f， 对吧？啊？一 f 好当的话，其实你也可以就，呃，不用这么麻烦，对吧？不用搞成一个数组啊，你也可以，因为呢，我们其实也可以搞成一个字母串啊，也可以啊，比如说我们这个二啊，那他是什么等于这个 abc， 对吧？好 啊，那这样的话斜起来比较快啊，这样斜起来比较快，然后呢三就什么就是 def， ok， 那这里的话，我们的四呢，就是什么 ghi， 对吧？啊， ok， 那是什么四就什么 ghi 啊，那这里的话，其实啊我们也不 不需要就说啊，这个就是一定是什么这样子的一个字，不算引号引起来啊，就三这样子直接写也是没有问题的好吧？ 啊，因为呢对于所引值来说啊，我们直接附近去自助串啊，他也是一样可以获取到这个具体的值，对吧？啊，是一样的，好， ok， 那我们再怎么再把这个五逗号啊，这个什么冒号 ghigmajkl， ok， 好，然后呢？六，那就什么 m o n o， 对吧？ 好，那我们的七七四码，七是我们的 pqrs， 八八就是 tuv， 对吧？啊？九，就是有四个值啊， wxyz wxyz， 是吧？啊？ ok， 这个也是有这个四个字啊， pqs， 好， ok， 那也就说这一个啊，他对应的这个字串，他映射就是长这个样子，对吧？好， ok， 那接着的话，我们啊就是说每一次我得到的结果，是吗？再传给下一个进行一个拼接不就可以了吗？对不对？ 然后呢，把每一次这种循环便利出来的东西，最终把它什么生成数组，把它添加到数组里面，是不是对不对啊？所以的话，我们啊就是啊，要搞出一个什么数组来啊，就这个啊，对吧？把每一次的这个什么最终生成的拼接出来的这个内容给他了吗？ 哎，放到破许到我们的 air 里面，好吧，好，那么这里的话他会给一个数字啊， 那我们肯定什么拼到最后我们才返回数字进行一个拼接，所以的话我们在这里画就什么定一个我们这个函数，对吧？好， dfs 在这里的话，我们啊就要什么定义这样子的这个地归函数，对吧？啊？然后去完成这样子的一个操作，那这个地归函数呢？我们肯定什么要有这个解，就是说从什么时候开始到什么时候结束，对吧？ 啊，所以的话，我们啊就是要传入这个，比如说啊，当前的这个循环到第几个，对吧？啊？比如说我二三，对吧？我已经 到三了，循环到三了，也就把最终这个三的所有的内容都拼接出来了，那这时候我们就是把停止，所以的话，我们这里的话就会有一个缩影值，对吧？好，然后呢，我们在这里的话，就什么把这个我们 这个什么数字啊，这个什么把它传进去啊，那这样的话传进去我才知道这个数字它的长度以及它数字里面到底有啥吗？要拼接啥吗？对吧？ ok， 好，然后呢，这个就是每一次拼接的结果啊， how resource？ 哎呀啊，那每一次的话就说啊，拼接的这个结果把它什么把它到时候就追，就说追加到我们的数组里面啊，你就说，哎，比如说我第一个就拼接 ad， 对吧？ a 啊，第一个是 a， 好，然后呢再把什么 d 拼接上来，对吧？把这个结果返回啊，就是把它破许到 a r r 里面啊，就是这样子的一个操作啊，就是这个就是结果，那就是啊，最终每一次第一规生成的结果。好，这个 这个呢就是我们的这个数组啊，哎呀，好吧， ok， 那也就是这个， 那当然的话，在这里的话，他都在这个函数里面，其实你不写这个和这个其实没什么问题啊，因为这两个都是同样的，对吧？ ok， 好，那接着的话我们再进行啊，一个判断啊，就一判断一下，一啊 index， 等等啊，等于什么呢？什么时候结束啊？就是我们的这个啊，当前的这个所引值啊，就循环到了最后，对吧？啊？就的 dress 的他这嘛本身的这个长度了， 好，那么已经到达最后了，那么我们就需要什么把这个最终我们拼成出来的 ad， 这样子的一个结果啊？就这个结果 我们干嘛呢？我们把它啊，如果有值的话啊，首先判断一下有没有值嘛，对吧？如果有值我们就进行 pose pose 到啊，我们的这个 ar 里面，好吧？ ok， 好，那如果不是呢？对吧？啊？不是就什么继续递规吗？对吧？如果他现在还有什么还有这个内容啊，还可以继续什么拼接，那你就什么，你就需要继续拼接下去，对吧？啊？那就什么循环进行一个什么便利的拼接啊？哎，等于零， 好，哎，小雨，是吗？那每一次那我们都要什么？就是拿出我们的，比如说我们现在拼到这个三，对吧？那三的话他有 df， 对吧？那就要拿出这个第 df 来进行拼接，对不对？ ok， 好，那要拿出这个 df 进行拼接的话，那么啊就什么把这个 obj 这个什么只取出来吗？ obj， 对吧？括号， 那这个是二三四五六七八，那这是到底是二还是三还是四呢？那什么就从这里面循环到第几个就是第几个吗？对不对？那就把这个 取出来，对吧？啊？ ok， d igits， 那这里的话他是什么？他是这样子的二三的一个什么数字字不串，我们要取出，是吧？第第几个缩影值对不对？那所以的话我们在这里画就把什么这个缩影值给他加上， 好，然后呢？啊得到他什么长度来进行循环，对吧？ ok， nice， 好，那循环完了之后什么我们这个什么进行一个地规的 一个拼接，对不对？好，每一次是吗？这个缩影值加一对吧，然后呢？把这个就是原封不动的传下去就好了，对吧？啊？然后的话我们的这个 rest 加上，对吧？上一次的结果啊，这一次的结果，再加上什么？加上我们现在循环到了什么第二个值，对不对？那什么把这一个取出来，他什么第二个进行一个什么拼接啊，对不对？ 好，然后呢？再把这个什么哎呀传进来，好，那这样的话，我们啊就，就最终的话，就什么，呃，就可以一直递归下去啊，把这个数据铺许到我们的这个数组里面，好，然后呢？最终啊，当然的话，我们一开始要有个什么起始啊，对吧？起始一开始的这个什么函数的吊用， 对不对？那所以的话零啊， digits， 对吧？把它传进去，然后呢？我们一开始吗？就是空字不串，对吧？啊？没有拼接任何内容，好，一个个什么往里面传就可以了，然后，哎呀然后放进来啊？ ok， 好，然后呢？最终我们锐腾一下我们的这个内容， 那现在的话啊，我们来看一下我们当前的一个结果啊，我们进行一下提交 啊，当然的话，这里的话，我们啊肯定是有一个报错啊，他这里报了一个小错误，我们一起来看一下，检查一下啊，这应该就是一个很简单的错误了，他说我们这个这个什么未定义，对吧？这个我们看一下，这里的话，我们其实有一个问题，就是说我们在 这里面，你看循环相等了之后，其实破许进去，我们是不是应该要什么跳出循环，对吧？啊？是跳出这个地规，所以的话，我们这里的话 retonforce 我们要给他什么加上啊？ ok， 那这样的话我们这个操作就没有问题了。 好，那么我们现在就可以看到啊，我们这个最终啊这个数据就生成出来了，当然的话 我们啊可以看到这一个还是很不错的，对吧？他这个速度和效率。那接着的话我们把刚才我们提到的，其实啊就说到，呃，像这一块啊，就是说我们既然都是在这个作用域内，所以的话像这个啊可以什么 把它给它去掉，然后呢？这个竖着，哎呀，我们也可以把它去掉。好，那这里的话也是一样的，这个不变的，我们可以这么把它去掉，然后这个我们也可以去掉，然后这个也是一样啊，我们去掉，去掉。好， ok， 那这样的话我们这个就啊把这个 啊不需要用的地方，我们喜欢把它去掉，然后呢我们再次提交一下，那么这样的话也是没有问题。 好， ok， 那现在的话我们这一个操作就解决了，那么我们啊这一节就讲到这里啊，大家好好的把这样子的一个地规和便利给大家搞清楚。好， ok， 那么我们这节课就讲到这里，拜拜。

大家好，今天给大家讲一下规定排序。首先我们来看一下规定排序的原理。好，我们这里有一个数组，我们希望将它进行排序， 在规定排序法当中使用的是分制的思维，所以我们这个时候想将这个速度分成两半， 然后分别对他们进行排序，排好序以后，然后再给他合成一个有序的完整的一个数组 啊。当然我们这个小的数组依然要进行分制，就是继续拆两个的，还要拆我们这样子，最后拆下来 到整个末端全部都只有一个元素的数组，一个元素的数组相当于是一个有序的一个数组，那这个时候我们可以将这些有序的数组进行一个规定， 就是把它们合在一起，但是这个时候我们进行了排序， 这样不断的合并，合并到最后啊，就得到了一个完整的一个有序的数据 啊。但我们这个 ppt 上是一个向下的，但实际上他是一个有底层不断的向上 规定的这样一个过程。 规定排序法和我们的快速排序 很接近，因为他们使用的都是分制思维，都使用了地规调用，但他们也有区别。我们快速排序法了是一分为三，就是一个数字，我们分成三份，中间有一个数据以他作为标准来划分， 而规定排序法是直接从正中间一分为二。规定排序法是先分解，就是把它分解成一个一个的小数组以后再进行排序。而快速排序法呢，是一边分解一边排序。 快速排序法是在我们原数组里面将这些数据进行排序，而规定排序法来需要一个额外的一个临时空间来存放排序的结果 啊，如果大家对快速排序的话不是很了解，可以看一下我前面的一个视频。 好，我们来看一下这个规定排序瓦的代码。在规定排序的代码当中，我主要划分成了两个函数， 第一个函数，它的功能是将一个大的数组不断的拆分拆分，最终拆分成只有一个元数的小数组。 第二个函数，他的功能是将两个有顺序的数组规定成一个有顺序的大的数组， 他们两个是相反的一个过程。那么首先来看一下这个函数 的实线原理。好，我们来看一下如何将两个有序的数组规定到一个更大的数组里面。我们需要三个指针分别指向三个数组的第一个元素， 然后我们判断左指针和右指针他们指向的数据哪个更小，比如这里六更小，那我们就将这个数据放在这个结果数据的第一位，然后将他们移到下一个位置， 这个时候我们再来判断他们指向的数据谁更小，比如这里十六更小，那么我们就把十六放到这里来，然后指向下一个元素 十八和二十二十八更小。 好，这个时候要注意了，我们这个左数组和右数组，这两个数组当中，其中有一个数组里面的数已经取完了， 那么剩下的一个数据里面的数据呢？我们可以将它直接移到我们的结果数据的位置上，比如这里二十二和五十六，我们直接放在这里二十二、五十六。 这一步做完以后，我们就已经得到了一个有序的这样一个速度，我们要将它移动到原先的原始速度里面，也就是这个里面。好，第一个我们就 将它赋予六，第二个元素呢是十六， 第三个元素是十八，第四个元素二十二盒五十六。 其实我们这里发现一个问题，就是如果说最后是右边这个数组没有取完数据的话，那么我们不需要将它移到这里面来，因为这里本身就是存放这几个数字的位置啊。如果是左边的数组 没有取完的话，那这个是肯定需要先移上来的。好，我们再来看一下具体的代码。首先我们来看一下参数啊，这个就是我们排序的 数组，这个 left， 他是我们的左边那个数组的开始位置的缩影啊。 red， 他是我们右边数组的开始位置的缩影，按的是我们数组的最后一个元素的缩影 啊，这个是我们临时的数组，也就是我们临时存放排好数据的那一个数组的地址 啊，在这里呢，我们首先定义了一个变量 star 等于 left 啊，是用来记录一下我整个数组的最开始的位置， 然后我们使用这个 red 减一啊，我们知道这个左和右是通过我们前面的函数当中拆分的，他们两个其实是在同一块相邻 的内存当中，所以 night 减一就是 nafta 的最后一个元素，我们找到就第一个数组的最后一个位置， 然后这里 p 等于零，这个 p 呢就是我们用来指向到这个零时速度的这个位置的一个缩影，相当于一个指针，就是我把结果存在这里开始的地方。 好，下面呢我们这里进行了一个判断啊，如果说我左边的数组 没有取完，并且右边的数组没有取完，那么我们就循环的取数据啊，所以在这个循环里面呢，就是取数据啊，从左数组和右数组里面取数据到我们的结果数组里面， 如果说我左边的这个数据要小于或者等于右边的这个指针指向的这个数据，那么我们就把左边的这个放到结果里面，因为我们先放小的，这是从小到大的排序， 然后将指针的位置加加，那如果说我们的数据是右边的要小一些呢，那这个时候就将右边的这个数据放到结果的这个位置 啊，也就是判断这两个指针里面哪个小就放哪个。然后如果一旦其中有一个数据里面的数据取完了，那么整个循环也就结束了。 巡防结束以后，并不一定代表我们所有的数据全部都取完 完了，这个是要检查一下，如果左边的数据没有取完，那么我们就将左边所有的数据依次的存入到我们的排序的数据里面， 而右边的我们就不需要，刚刚我们已经说了，因为右边它本身就是存放的那些更大的数，如果没取完就让它放在那里，我们可以减少一些数据的传输的代码。 好，最后一步呢，就是将我们临时的这个排好顺序的这些数据一个一个的 存储到原始要排序的这个数组里面去，从十大这个位置我们记录的这个数组的开始位置开始，一直到我们所有排好顺序的这些数据。 好，这就是我们规定两个有序数组的这个代码，那么我们再来看一下拆分的这个函数。 好，这个函数呢，我们首先还是看一下他的参数啊，第一个是我们要进行拆分的这个数组的 名字，然后第二个呢，就是我们目前拆分的这个数组的第一个元素的缩影和最后一个元素的缩影 啊。后面呢第四个参数，他是我们的临时数组，就是用来存放结果的这个数组。嗯，在这些代码当中，我 一直在传递这个临时速度，看起来好像是有点，嗯，麻烦，我们可以定一个工友的这样一个速度也是可以的啊，但是出于封装性的考虑，我把它坐在函数的参数里面 啊，但为什么不在函数内部再来定义这样一个临时数组呢啊？因为我们这个地规过程呢，他会嗯调用很多很多次函数，那么每次都去申请一块空间呢，这样子性能上的一个消耗就非常大 啊，所以我们嗯直接传递一个每次使用的时候都使用的同一个数足，因为我们知道他是引用类型啊，传过去以后，其实每次使用的时候都是同一个物理地址，同一块内存区间。 好，我们来看代码在这里面怎么拆分呢？首先我们这个是要使用地规的，要有一个退出的机制，就是说如果说我们的最后一个元素的缩影 小于等于第一个元素的缩影，那么就是说他只有一个元素的时候，或者无数据或者一个元素的时候，那么我们就不需要拆分了 啊，这就是一个退出的机制。然后下方呢就是进行一个拆分，拆分的时候我使用的方法呢，看上去有一点复杂，可能有更简单的方法啊，他们通常是使用的什么方法呢？就是说 最大的这一个缩影加上最小的这个缩影，然后除以二啊，这种方式也是可以的，但是我 觉得这种更好理解啊，就是最后的这个缩影位置减去第一个缩影的位置，然后加上一，这个时尚就是我们元素的个数，元素的个数除以二， 那么就是一半的个数，然后再加上第一个元素的缩影，这样子就得到了我们拆分出来的右边的这个数组的他的第一个元素的缩影 啊，这个需要去理解一下啊。总之这个地方可能拆分方式有点不一样，但是它的原理都一样，就都是将我们这个数组 啊，从正中间把它拆分一下，拆分以后我们得到了这样一个数据以后，我们就在 这个地方进行调用，我们同样的将这个数组继续传下去啊，开始的位置跟这里是一样的啊，但是我们这个地方呢，就是用右边的数组减一，右边的数组减一，那么就是左边的数组的最大的元素的缩影， 然后把临时数组传传进去啊，这是我们左边数组的一个继续调用，这个意思就是说继续去拆分啊，这下方呢就是右边这个数组，右边这个数组，哎啊，这个第一个 是一样的，那么第二个呢，这就从右边的这个缩影开始，然后到直到结束 啊，然后把这个临时速度传进去啊，这就是把它一个速度拆成两两个， 然后两个分别再去吊用，有可能会继续拆，继续拆，直到他只有一个元素的时候，那么就反围了。 当这两个方法返回以后，就说这两个都已经只有一个，或者说都已经排好序以后，那么我们就调用下面这个，就是我们刚刚的这个规定的这个方法，就是将两个已经有序的 将它合并成一个有序的这种大的速度，就我们刚刚已经讲解过的这个方法 啊，左边的锁引，右边的锁引结束的这个位置，然后临时的这个速度， 这是我们规定排序的主要代码啊，但是有一点点啊，再说一下这个 方法的吊用啊，这里看上去是非常复杂的，所以呢我又增加了一个函数，因为在这里面呢，我们需要传一个临时的数组，又要传一些什么开始啊，结束啊这些，那么我们直接对他进行了个封装， 只需要传一个数组给他，然后临时数组我们在这里面生成，一次性生成，然后他的其实位置第一次的时候显然就是零啊，最后的显然就是他的数组长度减一最大下标，这样就减发了，吊用 啊，也是非常简单的。那么最后呢，我们来看一下我这个写的一个测试的一个代码，这个代码我前面已经说过了，所以我这里就不讲了， 我们只是测试一下，就是我们调用了一个快速排序法和规定排序法，他们对两个相同的随机数足啊，这里面呢，我现在是用的是十万的这个数据量，我们来看看谁的效率更高， 好结果出来了，通过这个数据我们发现呢，就是说在一般情况下，我们的快速排序法的效率更高一点 啊，规定排序法呢？他的性能会稍微差一点。好，我们今天就讲到这里。

什么是地规算法？从前有座山，山上有座庙，庙里有个和尚。和尚说，从前有座山，山上有座庙，庙里有个和尚。和尚说这个故事其实就是一个地规。在计算机中，地规通常指的就是一个函数，不断得调用他自己。 比如我们可以把和尚讲故事定义成一个函数，说出从前有座山，山上有座庙，庙里有个和尚。和尚说 而说的内容可以通过继续调用他自己来输出，但是这样就成了一个死循环。所以地规还需要一个终止条件。比如我们可以在每次说之前判断一下和尚是不是已经说累了，说累了就不说了， 直接退出函数，那么地规也就结束了。举一个实际的例子，求一个数 n 的阶程，实际上就是求 n 乘以 n 减一的阶层，而 n 减一的阶层又可以等 等于安减一乘以安减二的阶程，那么就可以用这样的地规函数来实现了。注意，安等于一时，阶程计算已经结束了，需要退出地规是不是很简单呢？关注懒洋洋，学习更多开发小知识！

大家好，这里是代码所养鹿，我是成员卡尔。这期视频呢，来给大家讲解代码所养鹿中二叉数章节的路径总和啊。那这道题目呢，提议就是给我们一个二叉数啊，同时呢，给我们一个目标值， 我们判断呢，这棵二叉树里有没有啊，从根结点到叶子结点的一条路径，这条路径的所有节点里的元素啊，相加等于我们的目标和啊。那这棵二叉树里边呢，很明显有这条路径吧，是吧，这样这样，这 是吧，这一条路径啊，从根结点到叶子结点啊，这个元素相加等于我们的目标和是吧啊，如果这个二叉数里边只要有一条啊，这种从根结点到叶子结点的路径啊，相 加等于我们的目标和啊。我我们就 return two 啊，否则呢，我们就 return force 啊。那这道题目呢啊，提议就是这样。那接下来呢，我们来看我们应该如何去解决呢？啊。 首先呢，我们看到一个二查数类的问题呢，我们就要想啊，如果使用地规法的话，我们就要确定我们的啊，便利顺序 啊，当然了，迭代法也是可以的啊。那关于地规法和迭代法呢，我都在代码所有录网站上啊，本期视频的文字讲解版啊，都给了详细的讲解和可以便于运行的代码啊。 那这里呢，我就重点给大家讲一下地规法啊。那说到地规法呢，我们还要说这个便利顺序对吧？啊，那其实这道题目呢啊，我们使用前序啊，中序啊，还是后续啊，都是可以的，为什么呢？啊？因为这道题目呢，我们也不涉及到，就是中 节点的处理逻辑啊，就是中放在哪里都可以啊，你是中左右还是左中右还是左右中啊，都可以啊。其实在上期视频中呢，在讲左下角直的时候呢，我们也有说过，就是没有中的。处理逻辑呢，那么他的前中后续啊，都是可以的啊。 如果这里呢，大家要是不太理解的话，后面我讲代码的时候呢，还会给大家说一下啊。那接下来呢，我们就来看这个过程啊。 这个过程呢，大家感觉哎，好像挺简单是吧啊，我们就是从根结点到叶子结点，我们就便利哎，收集一下这个元素哎，相加呢，是否等于我们的目标和啊，就可以了啊。那其实呢，这个 规则看起来呢是这样啊。但是呢，大家去写代码的时候就发现，哎，啊，好像很难自己独立去写出来啊。其实 很多二查数的题目呢，都是哎，看上去呢，好像规则很简单呢啊，我们就判断有没有这条路径相加等于我们的目标和就可以了啊。但是提笔的时候就不知道这个代码应该怎么写对吧？啊。那接下来呢，我们再来看一下这个代码应该怎么写啊。 那首先呢，我们是定义一个呃，函数啊，我们要确定了这个函数的返回值和参数啊。那么在这里呢，我们返回值呢，是布尔类型啊。 那可能有的同学呢会比较，就是疑惑哎，有的函数呢，他为什么有返回值啊，例如说你是布尔或者是印的啊，有的你这个函数呢啊，为什么他没有返回值，你就是个 word 类型啊。 就是在这棵二叉树里边呢，我们需要便利的其实是找某一条路径啊，只要某一条路径符合的话， 我们立刻就返回。那么在这棵二岔树里边，我们是不是没有必要去便利所有的节点呢？是吧，我们只要找到一条符合的路径，我们直接原地返回就可以了。我们在这棵二岔树里边，是不是没有必要去便利又节点呢？啊，也就是柚子树对吧？ 所以说呢，我们如何找到一条路径立刻就返回呢？啊，那靠的呢，其实也是返回时啊，而且呢，这道题目呢，还要求我们找到一个啊，这个合法的路径之后呢，就瑞特处是吧，我们是不是要把这个处呢，一路返回上去，返回到这个根结点啊。 所以说呢，我们这里呢定义是一个布尔类型啊。然后呢，是我们传入的参数是吧？吹 note 啊，这里边我定义成一个 note 啊。然后这里呢，我们参数里边还需要一个计数器啊，这个计数器呢，是一个 int 类型，我们定义成 count。 呃，当然了，这个下面还会有一个主函数去调用我们这个函数啊。那这个主函数去调用我们这个函数的时候呢，这里传入的就是跟结点啊。 啊，这里呢啊，传入的呢，就是我们的这个目标值啊。那有同学可能说，哎，你这里应该传入个零啊。这样呢，我们从根结点往下去变力的时候， 遇到一个节点累加，遇到一个节点累加，遇到一个节点累加啊。我们在判断我们这个 com 是不是和我们这目标值相等是吧？然后我们再判断是否找到了一条合法的路径啊。 其实这么想呢，是比较直接的，但是代码写起来呢，会麻烦一点啊。我们在这里呢，直接传入我们的目标值啊。在这里假如目标值就是二十二，直接传入目标值。然后我们遇到 到一个节点呢，我们就把这个节点数值做一个减法啊，遇到一个节点，我们就做一个减法。如果到下面到叶子节点，我们这个炕啊被减成零了啊，那说明什么呀？说明这个沿路的这些节点相加是不是等于我们的目标值啊，是吧。啊， 那这样呢，其实思路是一样的。代码呢，会啊，简单一些啊。那当然了，我这里写的呢是类似于 cj 家的尾代码啊。那大家如果是其他语言的代码呢，可以去代码所有录网站上本期视频到文字讲解版啊，去看其他语言的版本啊。 那好了。那这里呢，我们去确定了地规函数的参数和返回值啊。接下来呢，我们是不是要确定中指条件呢？啊，那在这里边我们的中指条件是什么啊？是不是遇到了叶子结点，我们 就要判断了，哎，这个遇到叶子结点了，或者遇到叶子结点了，那么这条路径是不是我们想要的路径对吧？啊，那如果我们的 note 啊，遇到叶子结点的特征是什么呀？是不是这个结点的左为空 对吧？啊，那同时呢，它的又也为 co， 那同时呢，这里还要再加一个啊，同时呢，如果我们的 count 等于等于零了啊， 因为我们的 con 传入的就是我们目标值是一路减下来的啊。遇到一个节点，就把这个节点值做一个减法，遇到一个减就做一个减法啊，一路减下来。如果我们到叶子节点了，把这个叶子节点值 再一减啊，如果等于零了，那说明什么呀？我们是不是找到了一条我们符合题目条件的一条路径啊，那么这里呢？我们是不是应该呃瑞特处啊， 对吧？啊，那如果什么情况我们没有找到一条啊，符合我们题目要求的路径呢？ 如果当然了，这个是一样的啊，我直接去写，直接去写 cont 判断了。这里边啊，如果我们依然是遇到叶子地点，但是 cont 它不等于零 啊，不等于零，也就是说我一路减下来，你就看他不是零，那么是不是这条路径就不是我想要的路径了，那么我是不是应该 return foce 啊？那这样呢，就是我们的一个终止条件啊。那接下来呢，就是我们的第三步啊，单层地规里边的 逻辑啊。首先呢，我们是先处理左逻辑啊，那么大家呢？可以发现，在这里呢，我没有对这个 nono 呢，做他是否为空的判断对吧？啊，他如果要是空的话，这里是不是就异常了呀，我们是不是就操作了空指人了呀，对吧？啊，那所以说呢，我们在这里呢，就是 如果向左去递归的话啊，在这里呢，先判断一下啊，如果你这个左部为空，我再向左去递归啊，那接下来呢，是不是我这个 cont 就要把这个对应的值给减下去啊， no 的 left 它的外用对吧？把这个这是减等于啊，就是把这个啊，你的左孩子里边这个值做一个减法啊，然后呢，我们再去向左去递规啊，向 左去递归 traversal no 的传入他的左孩子对吧？然后呢，再把 cont 传进来 啊，那这里呢？啊，其实呢，大家发现大家在做二叉数的题目的时候呢，其实向左地规就是这么写的是吧？但是本题呢，他不一样， 我们这里我们的地规函数是不是有返回值啊，是不是你这里向左啊，你向左去地规的时候，这里是不是有个返回值，返回回来啊，这个返回值告诉我们什么呀？是不是就是假如这个节点他的左方向左方向 左子数，或者说左孩子是否有符合我们就是题目要求的这条路径啊？那如果这里边返回处的话，是不是相当于告诉我们 这个左方向啊？假如说这个节点他的左方向有符合我们这个题目要求的这条路径啊。啊，说这个节点吧，这个节点好一点， 他的左方向啊，有符合我们题目要求的这条路径，那么我是不是这条路径呢？那这个返回值呢？假如返回的是处，我是不是要把这个结果继续向上返回啊？ 是吧？啊，也就是说如果你这里是处的话，我是不是要继续 return 处啊？ 也就是说你这个节点，这个节点他左孩子向左去便利的时候呢，这个左孩子的地规函数告诉你了，这个左方向有符合我们题目要求的这一条路径，这里已经返回处了。那么 你这个节点得到了左孩子的结果之后，是不是应该把这个处继续向上返回啊？是吧，这样我们的跟节点才知道啊，原来左方向找到了一条符合我们题目要求的路径，对吧？啊，所以说这里呢啊，我们要 把这个结果处理一下啊，如果这个结果返回处啊，我们就继续向上返回处，这样才能一层一层一层一层把这个处的结果呢啊，返回给根结点。那接下来呢，就是一个回速的过程啊， 有地规就有回速啊，那么我们还要把这个右方向的值呢加回来。那这里呢，又涉及到回速了啊，有同学可能又差异了，你这里好不容易把它减下去了，你这里为什么要给它加上来对吧？啊， 其实在讲解二杀数的题目里呢，遇到了回速呢，我都会给大家说一下啊。那这里呢？再给大家再去说一下啊，为什么要有这个回速啊？我们在这条路径里边啊，假如，假如在这里呢？啊，我们找到一条符合我们的路径啊。我们这个 count 一开始是二十二，一路做减法， 减到这里减成零了是吧？我们是不是要回退回退回退回退到这里，他是不是要重新变成二十二，然后继续向右去变利啊，是吧？ 那他怎么回退？他在这里边变成零了，怎么回退回退到这里重新变成二十二啊。那就是我们要把当初减去的节点，我们再给他加上来啊，再加上来，然后你再去变右面的啊，柚子数的节点的时候，你二十二继续再往下减是不是二十二再减八， 再减十三是不是啊，再去判断是不是符合我们题目要求的这一条路径对吧？啊，所以说呢，就是我们一定要有回速的过程啊。如果我们这里没有这个回速的过程，那相当于我们这个框的一开始是目标值吧，我们便利一个节点就做减法，便利一个节点就做减法， 那么到柚子树他也做减法啊，预热为节点就做减法啊。这样的话，你这个 count 相当于便利柚子树的时候，是根本不可能找到符合我们条件的这个啊，这条路径的啊，你就是一直做减法了，就没有一个回速的一个过程。 那其实呢，在上几期视频呢，二大数里边涉及到回速呢，我都会给大家讲啊，为什么这里有回速啊。那然后呢，我们这个向左变列的过程就写完了啊。那接下来呢，我们再来看 向右边立的过程，同样呢，我们要判断啊，右节点是否为空啊， 啊，逻辑其实是一样的了啊。这里边呢， ctrl 减等于 no 的它的右节点，它的 y 六啊。然后同时呢，我们的 if traversal 往后我们这里传入的是什么呀？传入的是不是孩子的右节点啊，传入孩子右节点，再把 cod 呢传入进来啊。如果呢，你返回的是处的话，我这里是不是也要 return to， return to 啊。然后呢，这里就是回速的过程，你这里边减下去，我这里还要给他加回来。 那这里呢，其实我们是把啊返回处的情况，返回处的情况都处理了是吧？如果到下面了啊，我们这个都没有去返回处，那么我们最下面应该 return 是什么呀？ return force 吧。 那这样呢，其实我们就把这个函数的实现呢，就给写完了啊。那大家发现这个代码呢，其实是比较中鱼的啊，但是我是为了把整个过程呢，给大家体现出来啊。那首先我们先来看这个 地规顺序啊，地规顺序的话，这是左，这是右是吧？啊，大家可能发现，哎，那这里是不是没有中啊？是吧？大家好像没有找到中的逻辑啊，如果中，我是这里啊，其实这里就是中，没有对终结点的处理过程啊。如果中 是在这里，那就是前序。如果把中放在这里，那就是中序，左中右是吧？如果把中放在下面呢？啊，就是左右中就是后续是吧？啊，所以说这道题目呢，你是前中后续都可以啊，因为他没有中的处理逻辑。你把中放在哪里都可以啊，就有一个左右就可以了啊。 那我再说一下这个代码为什么荣誉了呢？其实这里啊，这里是可以做一个精简的。这里是可以做一句做一个精简的。整个这三行代码，其实就可以写成 if traversal， 这是向左去便利是吧？那然后呢？我在这里直接就可以写个 count 减去，减去什么呀？减去 no 的他的左孩子的白柳啊。在这里 return 出 这三行代码，我都可以合成这一行代码。但是合成这一行代码，大家可能就体会不到回速的过程了啊，因为这个回速的过程，我就啊放在这个参数里了，就是靠它减去幼孩子的数值啊，传给下一层啊，地规的逻辑啊， 为什么在这里做隐藏了，因为我没有改变 ctrl 的值啊，是吧？啊，那我在这里啊， ctrl 做减去是吧？我在这里 ctrl 又做，加上我为了就是恢复 ctrl 的值 啊。你在这里呢啊，你是直接把这个参数里边的值呢，做了一个 ct， 减去你的 u x 的值，其实你并没有改变 ct 的值，也就是地规函数的 下面，你这个 ct 该是什么值还是什么值啊？那相当于呢，就是回速的过程呢，其实就隐藏在参数里了啊，那和我这么写呢，这个效果是一样的。但是我这么写呢，为了就是把这个回速的过程呢，给大家体现出来啊， 当初呢，我这个 com 一路下来啊，怎么把这个数值减下去的是吧，我回速的时候，我就要一路把这个减过的这些数值呢，就要都加上来啊，然后呢，我重新变成二十二了，然后我继续再去向右去变例。 其实这里呢，就是把回速的过程呢，体现的比较完整的啊。那当然整个这个代码还可以做精简啊，因为粒扣上他是给了一个主函数吗？啊，那整个这个函数和主函数还可以做一个整合啊。 整个这道题目的代码呢，可能也就是五六行的样子啊。当然了，那个经典版的代码呢，大家可能也分析不出来这个变异顺序了，也看不出来这个回速的过程了啊。 所以说呢，我是不建议大家呢去看那么经典版的代码。当然了，经典代码呢，在代码所有录网站上呢，我都有给出啊，那如果想进一步精进的同学呢，可以去看啊。 当然呢，我是建议呢，对二叉数呢，掌握不是那么牢固的同学呢，还是按照我的这个分析过程来啊，一步一个脚印的去感受这个 二茬树里边我们便利的过程啊，去感受这个回宿的过程啊。然后呢，再去看经典版的代码呢，其实你就知道啊，这个经典版的代码里边他都隐藏了什么对吧？啊，那好了，那这期视频呢，我就讲到这里了，这里是代码所养鹿，我是程序员卡尔。感谢大家的三连支持。

假设我们希望地规的解决如下问题，编写一个函数，其输入为 n， 该函数需计算所有丛林之恩的非负整数之和。下面展示了一些函数输入的简要势力，以帮助你更清晰的理解我们要实现的功能。许多人可能已经见过这个函数的迭代版本， 然而，如果你需地规的解决这一问题，应该如何去做呢？下面我将地规拆分成五步，让大家可以很容易的理解和应用地规。解决地规问题的首要步骤是问自己，函数最简单的可能输入是什么？ 在此例中，最简单的情况是，嗯等于零，我们知道结果也应该是零。最简单的情况通常被转化为地规问题的基本情况。地规函数的基本情况是我们能够提供明确答案的唯一输入。所有其他问题的谢都将基于这 基本情况。解决地规问题的第二个关键步骤是尝试一些例子，并思考这些函数的输入和输出是如何互动的。在这个问题里，一个有趣的可视化思路是将我们的核看作是以输入值为基底构建的一个三角形， 这样我们的和就是这个三角形中所有小块的总数。你可以尽可能尝试更多的例子。一旦我们有了一组例子，我们现在要进行的第三步是将大问题关联到小问题上，花些时间看看是否能发现这些案例之间存在着某种明显的关系。用这些例子将它具体化， 问问自己，如果我知道嗯等于四的答案，我能解决嗯等于五的问题吗？如果我知道嗯等于三的答案，我能解决嗯等于四的问题吗？一个你或许已经注意到的有趣之处在于，如果我们知道嗯等于 四的答案，我们只需要再加五就可以得到嗯等于五的答案。同样，如果我们知道嗯等于三的答案，我们只需再加四即可得到嗯等于四的答案。看起来这应该是一个普遍规律， 但如果有需要，请随时验证一些更大的例子。这将引导我们走向第四个关键步骤及总结这一模式。假设我们希望计算输入嗯等于 k 的和，我们可以通过首先计算直到嗯等于 k 减一的和来找到这个和。接下来我们要做的就是将 k 加到这个和上。 一旦我们总结了这个模式，最后一步，也就是第五步就是结合这个地规模式和基本情况来编写代码。实际上这并不是非常困难的，因为代码几乎可以直接从我们的基本情况和地规模式中生成。让我们更深入的探讨一下 对于特定输入，他是如何真正运行的。假设我们执行输入 n 等于五的这个函数，实际上会发生什么情况呢？我们会通过初始函数，然后遇到一个地规情况，该情况在输入四的基础上调用我们的求和函数并加五。 因此我们知道这应该在理论上给我们十五的值，但严格说来，这个函数尚未被评估过。 实际上，最终我们必须重新返回到我们的函数并重复此过程。我们会再次遇到一个地规情况，导致我们需将四加到对三的调用丧的结果上。这一过程也再次触发了之前相同的程序。 我们来花一些时间仔细观察这个过程是如何进行的。因此，这个过程会持续下去，直到我们遇到基本情况，然后来解决对恩等于一调用的丧函数， 再来解决对 n 等于二调用的桑函数。如此这般，直到我们最终构建出对原始的 n 等于五的情况的解决方案。花时间展开地规以确保事物运作正常总是有帮助的，但当你在解决这类问题上变得更加有经验时，有一个我希望你能考虑的概念及地规信念跃迁。 地规信念跃迁可以使解决地规问题变得更迅速。这基于这样一个假设及问题的更简单版本会是正确的。 在这个特定的问题中，地规信念越迁意味着，如果我想解决对嗯等于五调用的 sun， 我只需假设对嗯等于四的 sun 是有效的。然后，如果我将五加到那个值上，对嗯等于五调用的 sun 也将是正确的。 如果你对地规信念越迁感到有些不确定也没关系，但这是一个有意的解决问题的工具，可以帮助处理 更为复杂的地规问题。现在，我们用之前的知识来探讨一个更复杂的地规问题。这个问题是这样的，编写一个函数，它需要两个输入 n 和 m， 并输出从 n 乘以 m 的网格的左上角到右下角的唯一路径数。 一个关键的约束是，你一次只能向下或向右移动一个单位。在我们开始应用五个步骤之前，我们先了解一下这个函数的一些输入和输出。当 n 等于二， r， m 等于四时会发生什么？ 我们得到正好四条路径。这是另一个例子，其中嗯等于三，而嗯等于三，我们得到了六条唯一路径。现在让我们用五步法进一步理解。让我们试一试一些简单的输入，看看会发生什么。这个函数最简单可能的合理输入是一个一乘一的网格， 我们会得到正好一条路径。如果我们实际上花一点时间尝试一些其他简单的输入，你可能会发现一些有趣的规律。我们实际上可以通过注意到，如果这两个维度中的任何一个是一，我们只有一条唯一路径来构建一个相当全面的基本情况。 这可以写的相当简洁，作为以下的基本情况。通常在确定基本情况时，你会想找到一种尽可能全面的方法，但是不要害怕，做出调整， 稍后返回并修改基本情况是完全可以接受的。现在，我们来观察足够多的例子，以更深入的理解这个问题。在为地规问题构造例子时，有意识的选择大量彼此紧密相关的例子是有道理的。 记住，我们的最终目标是找到一种方式用更简单版本的案例来解决任何特定的案例。 所以拥有彼此紧密相关的例子是有意义的。既然我们有了一组足够大的例子，仔细观察这些，看看你是否发现了案例之间的任何有趣的关系。我知道这里有很多内容，所以作为提示，我们将注意力仅限于这三个例子。 你发现了什么吗？现在呢？实际上，在二乘以三和三乘以二的情况中，每条路径与三乘以三情况中的每条路径之间实际上都存在着非常精准的一一对应关系。 对于二乘以三的情况下，我们可以沿着每一条路径向下走一单位，这样就在三乘以三的情况下生成了一条新路径。 而在三乘以二的情况中，我们可以沿着每条路径向右移动一单位，从而也在三乘以三的情况下得到了一条新路径。因此，在这个例子中，我们可以确信三乘以三情况中 中的路径数量实际上是二乘以三情况与三乘以二情况中路径数量的总和。这仅仅是个巧合吗？我们来看看是否能通过反向工作来验证这一模式。我们尝试通过分析一组更简单的相似例子来寻找三乘以四情况中的路径数量。 依照之前的模式，我们会观察三乘以四情况中的路径数量是否确实等于三乘以三情况和二乘以四情况中的路径数量之和。我们会将三乘以三情况中的每条路径向右移动一位，已构建三乘以四情况中的对应路径。 接下来，我们会让二乘以四情况中的每条路径向下移动一位，构建出三乘以四情况中的对应路径。这一构造展现的结果皆是生成的路径集合完整的覆盖了三乘以四网格中的所有独特路径。如果你有所怀疑， 花一点时间自己验证一下。现在我们来将这一模式进行概括。我们可以通过首先查找 n 乘 n 减一网格中所有唯一路径来确定 n 乘 n 网格中所有唯一路径的数量。 这些路径中的每一条都能对应到 n 城按网格中的一条路径，因为我们所做的仅仅是向右移动一单位来创造一个相关路径， 而余下的路径可通过查找 n 减一乘按网格中所有的唯一路径得到。我们仅需将每一条路径向下扩展一单位便能得到 n 乘按情况中的相应路径。 一旦我们找到了这一通用关系，最困难的部分便已完成。我们需要做的最后一步是将这一通用模式与基本情况结合，然后开始编写代码。 对于这样一个初看起来十分庞大的问题，最终得到的代码却出奇的简练与优雅。你会发现，在地规问题中，这是一种常见的现象，更多地规问题大家可以多加训练。

这一讲呢，我们继续呃接着上一讲回速法求解零一背包问题的内容， 然后增加了这个减脂策略来优化这个求解零一背包问题的算法。那我们现在回顾一下这个问题，零一背包这个问题啊， 有 n 个重量，分别为 w 一到 w n 的物品，他们的价值分别为为一到 v n， 然后给另一个容量为 w 的背包呢，我们要从这个物品当中选取一部分物品放到这个背包当中，然后有两个约束条件，一个呢是这个 放入的这些物品呢，重量需要等于这个 w， 另外呢，我们需要选择价值最 高的那个物品组合，这就是这个呃问题的描述。上一节课呢，我们呃通过回速法已经 找出来了，通过这个紫吉数的算法已经可以求解出来这个灵异背包问题里边的最优的组合就是这条。 最后呢，重量是六，价值是八，最大价值是八，那么这个算法呢， 能不能来对他进行优化呢？那么这次课的增加的这个减脂策略呢，就是 对这个自极术回速法的一个优化。 我们来先来看一下改进，一是左减值，左减值呢，也就是说对左指左指数的减脂策略。我们来看一下对于第 i 层的有些节点，第 i 层的有些节点 t w 加 w， i 已超过了这个已经超过了这个背包的能承受这个总重量 w 了，那这 在这个例子中呢， w 等于六，是吧？这个时候他已经，你看对于 di 层的这些节点加入以后，他已经超过了这个 这个这个 w 了，那么显然再选择这个 w i 就不合适了，他已经超过了，放不进去了，是吧？ 如比方说第二层的五四这个节点，第一层是那个根节点是吧？第一层是初始状态的根节点，所以说这是第二层这个第一个物品放进来的时候，五四这个节点 如果进行扩展，你看进行扩展以后呢，这个节点就变成八八了，这八很明显他就已经大于这个六了，已经装不进去，这个 其实第二个物品呢，就放不进背包了，对不对？那这个时候呢，是不是这个左子数就没必要再扩展？ 因为他你再扩展他也不符合这个约束条件了，因，因为他放不进去，是吧？这个大家看明白了吗？ 因为这个加入的这个节点的时候呢， t w 已经大于 w 了，它是八嘛？大于六了，所以呢，这个左字数就可以减掉了，是吧？没必要再往下扩展，这就是左减尺， 左减值呢，只扩展满足 t w 加 w i 小于等于 w 的左孩子节点。 t w 记录的是不是已经放入背包中的那些物品的总重量？ w i 是当前要放入背包中这个物品 的重量，是吧？如果他们加起来他还小于等于这个 w， 说明把这个 w i 这个物品是不是就可以放进去啊？如果他就已经大于这个 w， 说明这个物品放不进去啊，因为他已经超出背包的最大重量了，对不对？ 那么这样左剪枝以后呢？嗯，构建的这个子积树呢？就是这样的，因为你看都是左子树被剪掉了， 这五四这个节点再往下加，再往下扩展的话，是是不是八八？刚才所以这个坐姿处剪掉了，包括这个五四坐姿处剪掉了啊，这呢这个五四，因为他是加了最后这个物品，是吧？他是六五没有超过那个重量，所以可 可以扩展是吧？这边呢都一样，是吧？这呢都没有超过那个重量，所以呢就符合这个要求了。然后左减脂以后的这个字迹数呢？就是这样子。 那么左减脂完了以后有没有右减脂呢？右边这些是不是满，是不是可以减掉，省一些便利的时间呢？ 那我们先来看一下左剪织完了以后这个代码和前面的这个代码的区别，是吧？我们 没有减值策略的时候，这个代码前面的这个这个代码，这个低规的结束条件，这个都没有，没有变化是吧？有变化的就是这一部分，这一部分没有。这个昨 剪制的时候呢，他没有，他不需要这个判断条件是吧？他直接上来就是选择这个节点，或者不选择这个节点，然后进行定规。那么现在呢，有了左剪制呢以后呢，他就要判断是否 选择这个节点了，对不对？那这个是不是刚才这个条件啊？如果这个 t w 就是说已经加入背包中的物品重量，加上我现在要往里加的这个当前物品的重量，如果 超过 w， 那那就是不是就不需要扩展了？因为他放不进去，只有在他们的和重量和小于等于这个背包的总重量 w 的时候，才需要往下扩展， 是吧？然后这个因为一这儿没有又减值，所以这个这是这个柚子树，这没有变化是吧？那我们继续来看又减值，又减值是什么呀？又减值呢？上来他给了一个这么一个 rw 这个变量，也就是 r w， 就是右半部分右子数的总重量，你看从当前节点开始，是吧？从 w i 这个节点开始， 他的那些还没有加入背包中的那些物品的总重量，也就是 w i w i 加一直到 w n 这个呢？这个，这个也就是说从 i 这个节点开始，后边的那节点都还没有加入本，还没有选择呢， 是吧？现在呢？这个这个未选择的这些之后的这些节点，这些物品的总重量，那我们计算出来，用 r w 来记录， 当不选择物品 i 的时候，不选择物品 i 的时候，是不是那个那个那个分支上节点是标记是零啊？是不是就是柚子树啊？ 不选择这个 i 的时候呢？那就把这个说明 r 从 r w 减去 w i 呢？它等于 w i 加一到 w n， 这个大家能看明白吧？如果不选择这物品，那这那这个总重量是不是减去这个 wi， 这等于这个如果 tw 加上这个 r w 减 w i， 比如说 t w 是已经加入背包中用品总重量，对不对？那它加上这个值 仍然小于这个 w， 也就是说我把除了因为 wi 是幼分值，对不对？ wi 我不要，那除了这个 wi 之后的那些节点， 我都把它加到这个背包里边，对不对？我把这些节点呢都加入这个 t w 都加到这个背包里边，这个时候呢，它的重量呢？还没达到这个 w， 如所有的物品都加进去了，它的重量还没到达到这个背包的要求的这个重量，那这个时候呢？是不是也就不需要再考 考虑这些扩展这样的节点了，因为你除了这个 wi， 你不加入以后，这又分值，对不对？ wi 这个节点不要，然后他是零，然后后之后的节点所有的节点都加进去，他还到不了那个六 那个背包，那要求那个重量，那你加入这个，那这个组合序列他是不是就不满足这个要求了？所以说从 wi 之后的这个节点是不是都没必要要了，这样的话就实现了又减脂 又减值呢？只扩展满足这个 t w 加 r 还是 w 减 w i 大于等于 w 的，又还是节点，是吧？也就是说那些后边的之后的那些那些物品， 某一些物品加入到这个背包里的时候，他还能重量还能达到这个还能等于这个 w， 这种情况他才能满足这个重量的要求。如果那后边那些所有的未加入的物品加起来的重量 都达不了这个背包的要重量要求，那是不是就不满足运输条件了？ 那么我们来看一下这个又减值，是吧？又减值，你看 初始状态，这是根节点啊，这是根节点，初始状态零零呢？是一个是 tw， 就是当前物品的重量总重量， tv 当前物品的总价值。然后这个 rw 呢？就是 还没有加入这个背包的，还没有选择的，仍然没有选择的那些物品的总重量，是不是就是这个盒呀？因为一个物品都还没有加入了，是吧？那这个时候呢？ rw 就等于十一根结点，然后呢？ 刚才也说了右减值，右减值肯定是选择右分值，右分值上的这个是零的时候，说明当前这个物品不加入背包，对不对？当前 wi 不加入背包，那不加入背包呢？那肯定，那他的 那那 tw 呢？这个时候是零，是不是 rw 减去 werw 是十一，那这个 we 是五，是不是就等于六啊？那这个时候呢？它还大于等于这个 w， 这说明他还成立，是不是？这这时候呢就可以扩展，那扩展到这的时候呢？是不是状态就变成零零六了？因为因为这个这个 rw 呢？他减去了，因为这个物品没加入，减去了五，所以说这个时候呢 rw 就成六了， 六是什么呀？就是喊这剩下的这三个物品的重量是不是？那继续到这个节点的时候，继续扩展 左子数，这可以是吧？左子数，因为他只判断他的总重量超过没超过那个六那个大，对吧？是吧？然后呢右子数呢？ 还是判断这个公式是吧？ t w 加加上 r w 减 w 二，这个时候呢？ t w 是零，这个 r w 是六， w 二呢是三， 那六减三是三，这个时候呢他已经这个大于等于 w 已经不成立了，也就是说三小于小于六了， 那这个时候，也就是说之后的这些物品，这些这这三，这这剩下的这些物品的总重量加起来，他也到不了这个六，所以呢是不是这个又分支也就没有必要扩展了， 这样的话就实现了这个右减脂，那么我们来看一下，这是最终的增加了左减脂和右减脂以后的这个子积数，那我们看一下，如果这样构建出来这个子积数，是不是 这个节点的数量就少了很多？那么我们在这个，那么我们的这个便利的时候，是不是也就少了很多很多？路径，是不是这样的话，这个效率就提高了很多， 最终的解还是这个六八啊，最终的这个最后解肯定是一，肯定是一样的，是吧？这个这样就提增加了这个减脂以后呢就增提升了这个算法的效率，是吧？ 大家来看一下啊，这个是增加了右减值的这个算法代码，前面的这个结束条件呢？没有变，然后这一部分呢是左减值，这前面我们左减值部分看到的，是吧？这个 是判断条件， 然后呢 这是右减值右减值的判断条件，也就是我们刚才刚才讲的这一部分这个公式，这个 tw 加上 rw 减 wi 大于等于 w， 那么看这个地规函数，这 同时呢也增加了一个参数 rw， 是吧？这个 rw 呢是记录的所有仍然没有处理的物品的重量，是不是？ 那么这个 t w 是已经加入背包的物品的总重量，然后 r w 减去 w i 呢？是，就是说因为它是幼分值，也就是说不选不选择当前 w i 这个节点，除了不选除了 这个 wi 这个节点以外，剩下的那个还没有选择的那些物品的总重量，加上这个已经加入背包的总重量，如果 大于等于 w， 那说明，哎，这后边这个还有可能，哎，这个有可能选择这个后边这个物品组合起来，他满足这个重量的要求，如果他总所有的物品加起来都小于这个 w， 那说明他就不可能达到这个 w 这个重量， 那是不是就不满足这个要求？所以在这呢我们进行了又减脂不满足这个要求呢，就不走这个里面这个诋毁了，也就是相当于不去便利那些后边的那些节点了，那么最后呢，我们再来看 一下对针对于这个算法的这个回速法求解临沂背包问题的这个算法的分析，因为在求解的过程当中呢，我们呃相当于是构建了一个子籍数， 而且它是两个分支的，相当于类似于二叉数是吧？所以呢，这个算法呢，在不考虑减之的时候，解空间数中有二的 n 次 n 加一次方减一个节点， 因为减脂的节点个数不确定，所以呢，我们在这里呢，算法分析的时候呢，我们先不考虑这个减脂是吧？所以呢，最坏情况下，算法的时间复杂度就是 o r 的 n 次方是吧？最坏时间复杂度如果有减脂是吧， 有一些有一部分节点剪掉了，那它的时间复杂度肯定要比这个 o r 的 n 次方要要要小，是吧？ 好了，今天，今天呢，我们就是在上一节的基础上呢，对这个求解零一背包问题的这个回速法增加了减脂策略是吧，提升了这个算法的效率， 嗯，下来呢，呃，希望大家能够将这个代码呢自己运行一下，运行一下，然后看尽量把这个嗯算法的这个过程 打印出来，是吧，这样呢，大家理解的就更加清晰了。