好，接下来我们来讲一个特别有意思的题目 它很好地演示了深度优先搜索应该如何进行“剪枝”。 >> 这个题目都没有出现在标，标题上啊，还卖个关子，郭老师。 >> 啊是吗？不是故意的啊。>>呵呵。>>这个题目叫做：拯救少林神棍。>>哇塞！>>它说的是什么呢 呃就是说啊，少林寺的镇寺之宝，是救秦王李世民的十三棍僧留下的若干根 一样长的棍子，他们的镇寺的棍子啊。 这个少林寺是李连杰这个当初赖以成名的这个电影啊。少林寺 这个寺庙如果没有这部电影呢，到现在大家还不知道它是什么东西，反正当初这个电影 我们同学有说我已经看了七八遍了。>>这个电影我都没有看过。>>啊我们有代沟啊。>>很土。>>代沟啊 没看过这个电影是没有文化的表现呐。 好，后来又有一个新少林寺啊，啊说，这个是刘德华演的电影，在这个故事里面呢 说的是在民国某年，少林寺被军阀炮轰，然后这些宝贵的 镇寺之宝，棍子都被炸成了N节长度各异的小木棒呐 好可惜。>>注意区别啊，我们那个原来的那个叫棍子。>>嗯，对。>>后来的呢叫小木棒。>>坏掉的叫小木棒。>>我经常上上课就讲成了 棒子。>>呵呵......>>然后大家就笑作一片了。 >> 一会这个，一会棍子一会棒的，确实很容易混淆，现在大家不要搞错了啊，木棒和棍子。 战火之后呢，这个少林寺方丈，刘德华演的啊，他想要用这些木棒拼回原来的棍子。 但是他又不记得原来到底有几根棍子 他只知道古人比较矮小，所以为了携带方便，棍子肯定比较短 它就想知道这些棍子最短可能有多短，多短啊。 >> 这个桥段真是。>>大家记得要干什么吗？就是用这些 木棒拼成一些等长的棍子，然后这些木棒还不能浪费，全部都得用上 然后你要使这些等长的棍子尽可能的 >> 短。>>对。 那比方说呢，现在有这么多根木棒，它们的长度分别是46、45等等啊。 你要用它们拼成若干根等长的棍子，然后 那些棍子的长度要尽可能的短，那怎么办呢？啊比如说我尝试一下 我试一下这个棍子的长度设成95，看看能不能成功。 那我们可以拿46下拼下来，诶诶，以下也拼，哦哦，OK 拼成了棍子长度95 OK了，但是呢，这个95会不会太长了呢，说不定还有另外一种棍子 的长度，能拼出比如说4根或者5根棍子，长度比95还要小 那么就是更好的棍子啦，那你可以试对吧。>>对，所以这就需要我们的这个 深搜 >> 搜索。>>来帮助一下刘德华。>>啊没错，没错，嗯 我们就用程序来解决啊，那当然输入就是N根木棒的长度 输出呢就是能拼成的最小的棍子的长度。 那我们得枚举啊，对不对啊？呃搜索也是一个枚举的过程吧 那我们就首先看这个东西要枚举什么呢？>>当然是要枚举这个可能的棍子的长度。>>啊，对，这是 最直观的想法。那枚举所有可能的棍子长度，那我们就从最根，最长的那根木棒的长度 一直枚举到所有木棒长度总和的一半，就可以了，对吧。>>对。>>因为，至少也得 呃弄出两根棍子对吧？当然你也可以说所有的木棒都是同一根棍子，那个就不用枚举，对吧 呃 然后对每根假设的棍子长度，我们试试它，试一下看看能否拼齐 若干根棍子，而且木棒都不能说我扔掉不要，啊都得要用上。 呃，那我们难道真的要每一个长度都去试吗？>>那肯定不是啊。>>为什么呢？ >> 那有一些本身的这个长度就，显然就不可能是成为，因为你的这个木棒的这个数量 是等于是一定的啦。>>啊木棒的总长度也是一定的。>>然后你构成的这个，呃有一些 如果棍子的长度的话，它就不能是这个木棒总长度的 这个因数，是吧？那么这种情况下，不是找出，啊那这种情况下肯定不可能拼 实际上这种情况下应该是多数。>>是很多啊，这个是很强有力的一个所谓的优化，这个就要解释了啊，就是 对不是木棒因数的那个长度，我们直接否定，就不需要尝试啦。 好，那现在我们假设要试一个棍子的长度啦，那我们怎么去尝试 拼成若干根该长度的棍子呢？怎么做这个事情呢 当然你可以手工的去做，就是，呃 就是根根木棒啦，上面有棒对吧，然后拼成了一根，你再试下一根，最后你发现 最后你发现拼不成了，多余的一些木棒，或者说少掉了一些木棒 >> 你就拆呗。>>那你就拆，对。你上一根棍子的拼法肯定有问题，你把那个上一根棍子的 拼法给拆掉，重新再拼，你，然后你一直拆来拆去，最后你可能要否定掉 第一根木棒，第一根棍子的这个拼法啦。 那最后你还是拼不成，那时候你只能否定它。>>这个棍子的长度。>>啊，就只能说你假设的这个棍子的长度是没有道理的。 啊反正就是，拆了拼，拼了拆，啊，最后可能就会把棍子的长度也给它否定掉。 那现在我们这个问题里面所谓的“状态”是什么？啊我们 做深搜，广搜反正要牵涉到“状态”这个概念，这道题目“状态”是什么呢？ 嗯，状态可以是一个二元组，R和M。 这个R是还没有被用掉的木棒数目。 >> 就是可以继续往下，往下能来拼的。>>呃，你可以再从这个剩下的木棒里面拿出来 去拼新的棍子。M呢是当前正在拼的那一根棍子还缺多长 就能成为一个完整的棍子啦。 啊我们这个题目的状态就是这样一个二元组。那这个状态的选取其实也不是那么容易想到的啊，得想想看了。 那初始状态和终止状态是什么呢？这也是 我们需要解决的问题对吧？就是在初始状态和终止状态底下，这个R和M的值分别是多少呢 >> 初始当然就是这个N了啊，有N根木棒。>>有N根木棒了，对吧 >> 棍子的长度是你假设开始的这个L。>>是L，恩>>然后终止就是所有的木棒都被用到了 >> 啊。>>然后呢，棍子呢，当前这个待拼的棍子也都拼好了，所以是0。>>缺少的长度是0，对吧？所以终止状态就是（0，0），初始状态就是（N，L) 没错啊？好，那，那我们所谓的成功拼出若干根长度为L的棍子 那是干什么呀？就是要在状态空间里面 去找一条从这个（N，L)这个状态到（0，0）的这样一个路径。 OK，然后我们状态之间是如何转移的呢？ 我们看啊，就是从一个状态 上面我们 >> （R，M）。>>对，加了一根木棒，它就可能变成一个新的状态，对吧？从一个状态上面 剪掉一根木棒，也就是说在已经正在拼的棍子里面拆掉一根木棒，它也会变成一个新的状态，对吧，那比如说从（R,M)这个状态 记住啊，它说的是，呃 >> 剩了R个木棒。>>还没被用过，然后我们正在拼的那根棍子 >> 还差m的长度。>>对。>>就可以形成 >> 一根棍子啦 呃，是啊，那在这种情况下，如果我们拿一根长度为s的木棒 接到当前正在拼的这根棍子上面，然后发生什么事情呢 啊这个事情就是，哎，剩下的木棒的数目少掉了1们 然后我们正在拼的这根棍子它所缺的那个长度 就变成了M-S，那当然这里面有个前提就是S不能太大对吧，太大了就根本不能往上面拼 好，这是状态转移的一个办法。 那 >> 反之也是一样 >> 也是，对，如果对于这个（R-1，M-S）的话，我们拆掉一根长度为S的木棒 那情况会发生什么呢？啊 就说如果剩下的木棒数目是R-1，正在拼的棍子缺的 长是M-S，然后我们拆掉一根长度为S的木棒，那当然就变成了 状态变成（R，M)，对吧？这就是状态之间转移的这个方式。 好吧，那我们现在就演示一下这个拼凑棍子的这个过程。>>对，我们这里来看个例子 >> 嗯，我们假设有10根木棒，呃它们的长度都列在这了，啊 然后呢我们假设的棍子的长度是57。 >> 对，我们现在目前尝试的是以57作为棍子的这个 >> 这个初始状态就（10,57）了对吧？>>嗯。>>那现在我们看看这个状态之间 来怎么演化啊，棍子的长度没有记，看好了我们现在可以，呃，这个 >> 拼一个46。>>那这时候我们状态就变成9和 反应到（9,11）了，对吧？然后呢。>>剩下就是11啦，然后就发现说剩余的所有的木棒呢都不能拼了 >> 对呀，你就没有办法再拿一根放在这儿了，对吧？>>嗯。>>那所以我们就只好把这根棍子给拆了，就把46给退回去，是吧 >> 注意，是把这个木棒退回去，哦对，是把棍子拆了，把这个木棒退回去 >> 对，好了，那那就回去了，对吧？就回到了初始状态，深度优先搜索嘛，它在进行不下去的时候就是要回去了，对吧？那回到了这个初始状态，然后我们就会 哎，下一个木棒下来试试看，对吧，变成9，12 然后呢发现还是 >> 12还是不行。>>不行，啊它又回去了 然后呢我们再试这个36，呃36以后就变成了9，21，呃那36放在这还是 >> 有戏。>>放在这还是可以的对吧？哎，我们再拿一根木棒下来，就19看看，诶，变成了8，2。 然后呢 然后怎么办，然后就完蛋了，对吧，那我们就19这个就 >> 继续拆。>>继续拆，我们把，不要19，不要19呢又退回到这种，回复到这个状态了，然后就 拿一个16上来，变成8，5，那拿16上来，结果发现还不行的话 那就，哎我们就没辙啦，就说明这根棍子长度如果是57的话，它是 拼不成的了啦，啊。 呃基本上就这样一个过程。57不行的话，你得试下一个长度。>>对，重新更新 这个棍子的这个长度。>>对，那我们现在就根据这个状态 我们就可以写出我们的这个搜索的函数的bool Dfs(int R，intM)，啊 那这个搜索函数它的意思，它的返回值是true，或者是false啊，呃 这个函数做的事情是表示当前有R根未用的木棒，而且 当前正在拼的这跟棍子比假定的棍子长度还少M 求在这种情况下，往下做，能不能最后全部拼成功。 >> 等于就是深搜的还是每个状态呗，就说明R,M这个状 状态作为输入，一个状态作为起点往下走，看看最后能不能成功。 返回值为true就说明我们能成功。 那这个DFS这个函数有一个基本的递推关系我们必须得想， 因为它是递归调用的，所以它有边界条件， 那什么边界条件它得返回，继续递归，往下， 那当然就是如果r==0，就是没有木棒剩下来了， 而且，也没有棍子缺长度了，就是M==0，没有棍子缺长度，而且也没有木棒剩下， 都拼完成了。所有的木棒都用掉了，这时候我们就return true,就拼接任务完成。 嗯。不过，没有拼完怎么办呢？ 如果没有拼完的话那我们就找一根这个，当然一定是不能超过 剩余的M的长度的，就所缺的M的长度的木棒，然后假设它的长度为S的话， 那么我们就像刚才那个过程一样，我们把它拼在当前的这个棍子上，所以我们就生成了一个新的状态。以这个 新的状态重新进行进一步的深度搜索。这时候的话这个R就变成R-1，因为用掉了一个木棒， 而剩余的这个待拼的这个棍子的这个余下的长度就是M-S， 对，我们就从这个状态再往下进行DFS，看看能不能成功。 如果能成功我们当然就整个DFS就return true了对吧， 那如果不成功呢，那我们再去找找有没有别的长度不超过M怎么办， 再拿上来试一次。啊，如果所有这些长度不超过M的木棒拿上来试都不成功， 那当然我们DFS函数就返回false了。那好，如果我们找不到这样一根长度合适的这个 木棒S的话，就像刚才我们那57一样，对啊， 就是我现在缺M，我现在找不到一根木棒长度能够填到M这个位置上， 那我们就没法往下做了，对吧，这个时候，就返回false。 好，我们就返回false,这就失败了。 那么基本的递推关系就是这样。 下面我们来看看这个程序该怎么写。 这个N是木棒的数目，L是你假设的那根棍子的长度， anLength这是用来存放所有的木棒的长度的，这个anUsed这是一根木棒 是不是已经被用过的标记，然后这个是 深度优先搜索的函数，然后我们看到在main里面呢，把木棒的数读取进来，木棒数0的话就说明我们这个 这组所有数据都结束了，它是多组数据的一个题目。然后这是木棒的 总长度，这个while一开始是空的，然后我们把所有木棒的长度都读进来， 放到这个while里面去，然后这个总长度也给它算出来， 接下来我们这里有一个重要的事情，就是把所有的木棒按照 从大到小的顺序进行排序，这时候这个 调的是greater的这个函数对象，那我们为什么要从大到小 排序呢？当然很显然啦，你把这个短的呼噜呼噜拍好了就发现长的塞不进去， 啊，肯定不行。我们在拼一根棍子的时候我们拿剩下的木棒往上面接的时候 我们要优先去尝试拿长的木棒上来，还是拿短的木棒上来试呢？先试长的。先试长的，对吧， 因为长的不好安排，短的好安排，你短的很容易拼成功，你试了半天 发现那个长的没地搁，你前面那些短的都白拼了。对吧，所以我们做尝试的时候， 这个顺序很重要，我们要优先尝试那些长的木棒， 因此我们在这里把所有的木棒按照长度从大到小排序， 然后我们试的时候反正就是从这个iii的下标0开始往后试，那自然就 从大到小尝试了。呃，枚举这个可能的棍子长度L， 那么枚举这个可能的棍子长度L的时候，我们实际上 这个L你至少也得是最长的那个木棒的长度，对吧，否则的话，那个最长的木棒就没办法解决了。 嗯，否则的话，对啊，最长那根木棒就没办法放了啊，因为你棍子比最长 那根木棒还小啊，对啊，没错啊，嘻嘻，对了，好，那我们这个长度， 就成了anLength0开始，因为我们anLength已经从大到小排了，对吧， 下面这个棍子的长度 它我们要枚举的最长的棍子的长度呢，主要是全部棍子总长度 的一半就可以了，当然你也可以说，所有的木棒 都组成了一根棍子。如果L它是所有木棒的总长度的话我们就不用试了，就直接在这里给它输出就行了， 所以我们尝试的范围就是应该是0到anLength除以2，然后在这里面如果这个L它 不是nTotalLen的因数，就是这个nTotalLen除以L不整除，那当然我们也不用试这个L，对吧，直接就CONTINUE，试下一个长度了。 好，现在如果我们要进行尝试的话，我们一开始得把所有木棒使用的标记全部置成0， 一开始所有木棒都没有被使用过， 然后我们直接就去求答案，DFS，SL，就是 我们有S根木棒使用，我们要 拼凑的棍子它的长度是L， 这样做下去看看能不能成功，那如果 能成功我们就直接输出L就行了，因为我们 在这个枚举L的时候是从小到大，对吧，那我们找到了第一个要求的L， 就是整个问题的这个答案。要求的是 最短的可能的棍子长度，所以整个main程序的框架就是这样。 好，那我们再看下面，关键就是这个DFS怎么写。 好，DFS，RM，M表示当前正在拼的棍子和L比还缺的长度， R是还剩下R根木棒 可以用，那我们先看一开始就是一个边界条件，如果 已经没有木棒剩下了，而且也没有哪根棍子缺长度，那就任务完成， 对吧，我们就return true，那，如果M==0，就是说， 现在没有任何一根棍子缺长度，但是这个R它还不等于0，就是说还有木棒存在， 那这时候你要做什么呢？再新拼一根啦，对就是你要开始一根新的 棍子，那新的那根棍子它缺的长度是什么呢？L，啊就是L， 好，那接下来我们就开始去拼 棍子了，那拼棍子的时候我们就要在剩下的木棒里面拿一根上来 接在当前正在拼的这根棍子上面，所以我们就 遍历所有木棒，对于木棒 I我们要看，如果这根木棒还没有被用过，我才可以拿它， 对吧，那当然，这根木棒必须是没有用过，而且 它的长度肯定要小于等于M你才能够拿上来拼，对吧， 因为我们正在拼的这根棍子它缺的长度是M，你不能拿一根太长的上来， 假设有一根木棒满足这样的条件，那我们就把它拿过来，拼在 当前的这根棍子上面，好，那现在我们 前面已经把anLength就给它按从大到小 的顺序排序了，所以我们在这里尝试这一根木棒I的时候实际上是从 长拿到短，对吧，先拿长，现在我们把anUsed置成 1，说明我们用上了这个第i根木棒， 那么这个时候我们就发生了状态转移了，对吧，就 怎么转移呢？就是我们剩下的木棒就变成了R-1根，然后 我们当前正在拼的这根棍子它的缺的长度 就变成了M-anLength[i]，然后我们就 从这个状态再往下做，看能不能成功，如果能成功的话， 哎，就return true，任务就完成了，对吧。那如果不能成功呢？那我们就要回溯。对，就是我们 这个刚才拿的这根第i根木棒，你用它是不明智的，你不应该用它， 那你怎么办呢，刚首先就要把使用它的这个标记 给它清零，就说明我后悔了，我不用它，怎么办呢，然后你就回到这个循环， 选下一个i，也就说我拿下一根木棒，再往当前这根棍子上面去拼。 啊整个的过程就是这样。如果 这个DFS能返回true的话，它一定是在这个地方或者这个地方，返回， 如果它不能够从这两个地方返回true，那最后它就会return false，啊，如果你这里所有的木棒都拿来 试了，结果都不能够return true，这就说明这根棍子的长度 是不可以的。就是从当前这个局面往下走是没希望的。 在这里会return false， dfs就是这样的了，那这个程序基本上就算完了。 哎呀，可是这个题目是不是还有点 意犹未尽啊，对啊， 就是你想出了一个办法，但是这些和尚都会关心， 哎你这个办法挺好，可是要多长时间你才能够把这100多节木棒给我拼成棍子呢？ 你说和尚为什么要关心这个呢？ 他想早点拿到这些棍子嘛。是不是他当然得关心喽。那我就回答他，呵呵， 怎么着也得1万年吧。你说这和尚会怎么样啊， 咣当，崩溃了，这方丈就会出来说了，哎呀，请施主稍微快一点啊， 老衲在有生之年能看到这些棍子。那怎么办啊， 那我们就要加快搜索的速度，啊， 怎么加快？用剪枝的办法可以解决。 这这，什么叫剪枝啊，你搜索的过程像是一棵树在生长，对吧， 那我们把一些没有用的搜索方向，也就相当于一些枝条我们及早判断出来这个枝条是没有用的，我就咔 给它砍掉，我就不往下走了，这个时候就能够提高搜索的速度，啊，所以这个这样一个 及早结束某一个没有用的分支的搜索，这个事情我们就很形象的把它 描述称剪枝，好，那我们 在很多做深度优先搜索的时候 都要下。我们如何剪枝才能够使得这个深度优先搜索 的速度足够快，到达我们可以接受的程度，那总而言之就是要 尽可能的，尽快的发现没有希望的状态，避免从这个没有希望的状态往下继续尝试， 这就是剪枝的本质。那我们在这个问题上 在这个棍子的问题上有哪些剪枝的方案呢？ 首先第一条就是 不要在同一个位置多次尝试相同长度的这个木棒。 这个事情如果你手工来做的话你是很容易想到这一点的。比方说我刚才我拿一根长度为 N的木棒放在这个位置往下拼，就成功了，你 拆来拆去，然后把这根长度为N的木棒已经拆掉了，你肯定不会在同一个位置再拿另外一根长度为N的木棒来试，对吧， 就像刚才57对应好像有3根36，啊，对，如果你第一根36试完不成，你不会，第二根36，对对对，同样的 长度再，但是你写程序你可能就会忘了这一点。你手工的时候肯定不会忘这一点。 因为这个题目的数据里面说不定有好多根木棒它们长度都是一致的， 你在一个位置试了这个长度不行，你不可能再拿下一根相同 长度的木棒试在同一个位置，是吧？让你写程序的时候把这一点体现出来，我们刚刚那个程序没有体现这一点 所以这是第一种剪枝方案。很容易理解。 嗯，总之吧，就是某一次拼接选择长度为S的木棒导致最终失败， 就在同一个位置，尝试下一根木棒时，要跳过所有长度为S的木棒，就第一种剪枝方案。 这个题有各种各样的剪枝方案。有的剪枝效果特别明显，有的会稍微 有点作用。这种剪枝方案在数据 里面有大量木棒长度相同的时候就非常的管用。 那再来看第二种剪枝方案。第二种剪枝方案 它说的是，如果由于以后的拼接失败，需要重新调整第i根棍子的拼法， 那在这个时候，你不用去考虑去替换第i根棍子中的第一根木棒，为什么不用考虑啊，因为你换了也没有用。 那如果你不去替换第一根， 第i根棍子的第一根木棒的情况下，你怎么都无法成功，那我们就要推翻第i-1根棍子的拼法， 然后你不存在第i-1根棍子的话，那就推翻本次假设的这个棍子的长度， 尝试下一个长度。这个剪枝有点绕。对啊，就是，那我们要画个图演示一下。 好，就是说，如果这是一根棍子i， 它有三根木棒组成，木棒1，木棒2，木棒3，组成，我们把它拼好了， 然后再接着往下拼， 我们发现最后不能够成功了，现在我得把这个棍子i给它拆掉重新拼， 这个时候我们可以考虑把木棒2，和木棒3都给它拿掉来重新拼棍子i。 但是如果你把木棒2和木棒3都给它拿掉，然后你各种拼法 还拼不成，然后你想着，哎呀，光换木棒2木棒3是没有用的，我是不是要把木棒1给它换了。 再试试看。那你的这种想法就是没有道理的。 你按这种想法去尝试肯定也是不会成功的。就是你换掉1，是没有意义的。 主要是因为木棒1的话它始终会出现在一根棍子的，因为它已经是最长，就剩余木棒里头 最长的那根，它反正会出现在一根棍子，最前面的，你在这根里面拼不成，你在下一根还是会出现。 对，如果下一次能够拼成那么在当前这次也能找到合适的解。就是这个原因。 所以说，我们替换木棒1是没有意义的。这就是一个有效的剪枝。 那为什么第i根棍子和第一根木棒是没有用的？ 那当然就是你假设替换能够全部拼成功， 那么被换下来的那个第一根木棒它以后必然会出现在以后拼好的某根棍子k里面。 那我们原先拼第i根棍子的时候我就用棍子k的拼法去拼它，不就应该能够成功吗？对吧？ 这就是原因。好。 假设这是棍子k，木棒1出现在这。那我刚那个棍子i就按这个拼法拼，就OK了。 所以我们刚才这个剪枝方案说明了它的有效性。 好，那接着我们以这个举一个例子把，就是说假设 木棒10根，棍子长度是57，那我们把这个46放在这里， 我们，如果46放在这里我们发现 拼不成的话，按照我们前面的做法，我们不是把45拿上来试了，对吧， 这是我们前面的做法，但是如果我们写， 你看我们45不成功，我们又把36拿上来试了，在这里我们做的事情就都是 在重新尝试一根棍子的第一根木棒它的拼法。 对吧， 46不行，换了45，又换了36，但是我们学到了刚才那个剪枝以后我们就知道，46如果不行， 36换出来我们还试了19，还接着往下试呢，对吧， 但是如果我们有了这个剪枝2，我们就知道，你46拿上来不行，你马上就锁定长度57， 你不用再试了，为什么，因为你46如果在这里不行，你在后面肯定也不行。 这是剪枝2说的事情。那我们46换下来不行，我们 直接就锁定长度57，不用再像刚才一样再拿45啊，再拿上来试， 当然就会节省很多时间。接下来我们在程序里面，就要把这个剪枝2给它 就把这个剪枝1给它体现出来。 刚前面提到两个剪枝，一个剪枝就是说相同长度的木棒你不要在同一个位置试， 还有个剪枝就是，一根棍子的第一根木棒 你不用再去换别的木棒来去尝试了。 我们怎么体现这个剪枝呢，我们在这。 就是我们再找下一根要拿上来用的木棒i的时候，我们判断，如果 i大于0，就是 它在剩下的木棒里面不是最前面的一根了， 那我们就要看看它前面这根木棒是不是已经 被用过，如果它前面那根木棒没有被用过，而且它前面那根木棒的长度跟 我这个第i根木棒的长度相同， 那我们就continue,continue的意思就是我不用第i根木棒，那这个 这条语句就体现了剪枝1.，剪枝1说的是什么啊，不要在同一个位置 尝试相同长度的木棒，对吧。 这个为什么能够体现剪枝1呢，我们分析一下。我们要 想要尝试第i根木棒的时候我们发现，哎，那它前面那根木棒还没有被用过。 它怎么可能呢？我们拿木棒用的时候不是从大到小拿的，对吧，那我拿的 第i根的时候我就发现第i-1根居然没有被用过，为什么会产生这样的现象啊， 那第i-1根我们前面必然已经尝试过，对吧， 对，拼不成。对，就是我们前面尝试过第i-1根并且发现第i-1根是拼不成的。 我们才会后悔一下，把这个标记制成false，是吧， 然后发现第i根跟I-1根是相同的，对，而且你现在这个位置又是一样的，因为lm是一样的， 位置是一样的，那你在这个位置再去试相同长度的第i根当然就没有用了， 对吧。 就是，anUsed[i-1]==false说明我们前面已经试过第i-1根，不成， 那在这个位置你试相同的长度 相同长度的第i根当然也是不成，所以我们第i根这个就不能用，我们直接就continue，我们再试下一根了。 这个就是剪枝1.再看看剪枝2呢， 再看剪枝2.剪枝2在哪呢？剪枝2说的是什么啊， 呃，就是在一根木棒，把一根棍子拼不成的情况下我们要去 就是要去拆这个木棒，一直拆到 第一根木棒的时候，就不用，就是我们看到剪枝2 是在这，如果M==L我们就立成false，M==L立成false意味着什么， M==L说明什么，我们 这根棍子却的长度是L，是吧， 也就说我们在这一次尝试的时候，我们拿上来的木棒是这根棍子的第一根木棒， 结果在，我们前面在 注意我们在这里是拿了第i根木棒上来， 然后在这里就做了这根DFS看看能不能成功。 走到了这个else就意味着我们刚才拿上来的这根木棒是 不成功的。所以我们就后悔了，我们要否定 第i根木棒这种取法，我们否定第i根木棒这种取法，如果我们 发现了这个第i根木棒是整个棍子的第一根木棒的话， 那我们就不用再做下去了。这就是所谓的剪枝2，对吧， 那么我们怎么样知道这个第i根木棒是不是我们正在拼的这根棍子 的第1根木棒呢，就是M==L，哎我们如果这时候这根棍子它却的长度 是L，那就说明我们刚才拿出来的第i根木棒是作为这根棍子 的第一根木棒来试的。那这是第一根木棒不行了，我们要不要换一根 木棒上来作为新的第一根木棒呢？按照我们前面所说的剪枝2， 不需要换，换是没有用的，所以我们就直接return false，而不是 再做下一个循环，选下一个i了。这就是剪枝2. 那我们看到这一个程序用上了剪枝1和剪枝2. 好，刚才出去吃了顿午饭，现在接着讲。 嗯，讲到剪枝3了， 呵呵，还在撑着，还没反应过来呢，是吧，你对午饭 有什么评论？呵呵，我就觉得北京现在天好热，出去走一圈满脑袋都是汗， 我们说剪枝3啊，不要希望通过仅仅替换 已拼好棍子的最后一根木棒就能改变失败的局面。 这到底说的什么意思呢？它说的是比方说我们拼的某根棍子 i是这个样的，啊，然后我们发现后续再拼的时候没有办法成功了，我们就要把这第i根棍子给它拆掉， 那有一种办法就是我把这个最后一根木棒，也就是这个3，把它拆了， 然后我留下的空呢，就用其他短木棒来填。 这当然是看上去很有道理的一种做法， 但是我们这个剪枝3说的就是你做这件事情是徒劳的， 没有用的，那是为什么呢？啊，刘老师来说，为什么呢？ 呃，主要是因为说如果你现在能把这个3替换到其他的棍子当中， 然后把它这个后续，原来不能拼成的这个情况都拼成了，那 跟3所对等用来替换这一系列其他的小木棒， 那么同样其实也可以拼在棍子K这个位置， 3的这个位置，对，所以就说如果原来 这个地方拼不成，你去替换3，单独这么一根这个木棒 实际上是不可以的。如果你用别的小木棒来替换3 拼成了，那在 这个3会出现在后续的棍子k，那你把棍子k和棍子i这两部分对调一下不也应该成了吗？ 所以说，如果原来不成，现在依旧也成不了。 啊这个就是剪枝3，很管用。 好啦，就这一判断我们都已经说过了。 好，实际上我们还可以有别的剪枝，这个剪枝4. 它说的什么呢？就说，我们拼一根棍子的时候我们要确保已经拼好的部分 长度是按从长到短排序的， 就是说在拼的过程中要排除下面这种情况， 这种情况说的就是，哎，这个2是这根棍子第二根木棒，它却比这根棍子的第三根木棒还要短， 这个事情是不好的，我们要避免这种情况的 发生。为什么呢？我们有可能把3放在这个位置，结果往下做，做不下去了， 做不下去了，这个时候，那这个时候没有2嘛？这个时候2有可能被放在别处 地方啊，有可能也没有2，因为我们如果有3和2排在这个时候， 我们是先把3拿来放在这里，4的对吧，对，先把3放在这里，4 然后发现什么都做不下去了，于是我们就把3给拿走，是吧， 3给拿走，是吧，我的问题是如果有3又有2怎么会做不下去，这不1,2,3,1,3,2不就构成了， 就是再后面就做不下去了，哦，对OK我想起来了。就是当前这根木棍，棍子 对，是可以的，但是再往后就做不下去了，对对对， 是有这种情况。所以这个时候它就会把2放进去，然后底下后面排3，然后后面也可以向下排，对，对， 但是，但是这个剪枝意思就是说，如果你把 2摆在这，把3摆在后面，你再往下做，也一定是没有前途的。就是说，如果你当初把3摆在这，把2摆在 这，做不成，那么你调个顺序，也做不成， 这是明显的。但是我们写程序的时候可能就会忽略了这一点， 就是我们试这个位置的时候我们把3拿出来，后面我忘掉了，我又把2拿上去了，又把3排在这， 这都是徒劳的，这就是剪枝4. 好吧，那我们怎么样排除这种情况的发生呢？ 那就是我们每次找一根木棒的时候只要这不是一根棍子的第一条木棒， 我们就不应该从下标为0的那个木棒开始找。 就我们找木棒不是便利那个anf数组，每次都是下标为0然后往后iii，那这个方法是不好的， 我们应该从刚刚，就是最后一次接上去的那条木棒的下一条 开始找，那也就说我们这回找出来的这个 木棒肯定长度会比我刚刚接上去的那个要短，是吧， 这样就不会发生往2后面接更长的3这种情况了。 那为了这个目的我们就要设计一个全局变量叫做nlaststickno. 这个全局变量可以记住最近拼上去的那条木棒的下标， 对就是记录一下当前处理过的那个位置，只要 从这个位置往后去处理， 对，就会不会拿更长的上来了。 那我们再看下我们改写的DFS的写法，把各种 剪枝都给它体现上去， 首先我们要把剪枝4体现出来，我们说有一个全局变量，在这，nlaststickno 这全局变量，那我们在选取一根木棒的时候我们要从这个 startno.这个位置开始往后选取，但是这个startno的值呢它不一定是0，它有可能是0，不一定是0， 那如果我们发现这个nleft不等于l，这说明什么， 我们正在试图往上拿的这一根木棒，不是第一根，不是这根棍子的第一根木棒， 那么在这种情况下我们选取木棒的时候就应该从上次接上来的那一根木棒的下标 后面去进行，或i等于nstartno.， 到s-1，在这个anleft里面去找这个木棒， 这个就是这个剪枝4.那当我们要找到了一根木棒并且把它拼上去的时候我们就要 更新一下这个nlaststickno这个值了，这个剪枝4. 那剪枝3，是什么呢？剪枝3在这， 就是如果anLength[i]等于nleft，就代表 什么意思呢？这就说明你刚刚拿上去的这个木棒i它是 正在拼的这一根棍子的最后一根木棒， 啊，我们程序走到这的时候把nUnused置成0 就说明我们刚才想拿上来的那根木棒这个方法是不行的，我们后悔了，我们不应该用这第i根木棒， 那不用第i跟木棒的话，按照正常的情况 我们应该回到这个循环再试下一根木棒，对吧，可是我们剪枝3说的就是如果你发现 第i根木棒不行，而且你又知道这第i根木棒是我们当前这根棍子的最后一根木棒， 那你就不要在这个位置再去试别的木棒了，你就直接return false， 也就说不要再回到这个循环再试下一根木棒，这个就是 剪枝3，剪枝2我们前面讲过， 那我们专门写了一个剪枝的演示程序，我们来 直观的看一下使用和不使用剪枝的话在拼棍子的速度上面有什么差别。 那我们先看看，剪枝1和剪枝2都不使用的情况会怎么样。 您慢放还是快放啊？我 慢放吧。这个剪枝1指的是什么啊，剪枝1说的是 相同的位置不要尝试相同长度的棍子，对吧， 就不用重复了，36有几根？这36有三根对吧，看看这36 如果不使用剪枝1就会被重复使用，看啊， 一开始46，你看36 1，是第一根36， 来一直试的。 哎不行，同一个位置换36 2上来试， 当然就是徒劳了，我们看到还换36 3上来试，这都是徒劳了。 咱们看到没有使用剪枝1，多么的讨厌。 我们来停止。那我们来看看如果使用剪枝1会怎样呢，开始。 46 不行，45，36 1再这试， 好，哎，然后36 2我们就不会去试它了，对吧，当然就节省时间了， 我们看到这个是剪枝1它的这个作用，就有 3根36，那我们再看看这个剪枝2，如果不使用会怎么样， 剪枝2说的是就算我们用了剪枝1吧，剪枝2说的是 一根棍子的第一根木棒就不要去拆它了， 拆它也是没有用的，对吧，那我们看到，我们不使用剪枝 2的话对于这第一根棍子的第一根木棒做了各种各样的尝试， 45不行，46不行，又36又24，不停的去尝试， 实际上这都是徒劳的。我们如果使用了剪枝2就会发现， 4 46不行，马上锁定长度就到95， 当然我们就减少了非常多的尝试。对吧？好吧，那现在我们 比较一下两个剪枝都不使用，我们快放，看多长时间能把这个棍子给拼出来， 开始，拼啊拼啊拼，要 多长时间呢？它这个地方关键就是把57这长度跳过去了， 就等于全部有效，7秒，看看剪枝2是多么的有效，7秒。 好现在我们把这两个剪枝都使用上，我们再重来一遍，看看 速度有多快，瞬间就出来了，只需要0.3秒，哇，太惊艳了！对啊，可见这个剪枝是多么的有效啊。 OK，这就是这样。下面我们要总结一下从这道题能够学到的经验。 第一条最最重要的，就是要选择合适的搜索顺序。 在这道题上面的表现就是我们要优先尝试那些 长的木棒而不是短的木棒， 这个经验的本质是这样的，就是说如果一个任务分成ABC 等等步骤，在这个题目里面就相当于我要把1号棒子摆好，把2号木棒摆好，把3号木棒摆好，等等， 好了，ABC等等步骤，如果 这些步骤它们可能的方案不一样，比如说A这个步骤 它可能有50种做法，B这个步骤可能有100种做法，C这个步骤可能有200种做法， 那我们就要优先尝试可能性少的步骤，我们就要优先尝试A的这个做法， 为什么呢？因为如果你去先试了可能性多的那些步骤， 你全部都试一遍，最后发现大部分最终都没有办法求得 最终的答案，那你那些试了那么多步骤不都白试了，对吧，那你去尝试 可能性少的步骤呢，白试的次数就会少一些。这个是很显然的，这个经验特别重要，它适合于各种各样的搜索题。 比如说有的搜索题是类似于七巧板，给你一些 形状不同的方块，问你能不能拼成某一个大一点的形状， 就是说你就应该去先 去尝试那个面积大的那些小方块的摆放方法，然后再去尝试面积小的这些 小方块的摆放方法。 好，第二条经验就是我们要发现表面上不同但实质上 是相同的这些重复状态然后避免重复的搜索，在这道理里面的表现就是 有多根木棒它们的长度 可能是一样的，我们要排除这种情况。 第三个经验就是我们要根据实际问题 发掘解决方案，那当然就得具体问题具体分析了。
