算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
生日蛋糕
Loading...
From the course by Peking University
算法基础
284 ratings
From the lesson
深度优先搜索（2）
本模块继续通过两道例题，强调了两种最通用的剪枝方法：可行性剪枝和最优性剪枝的应用。可行性剪枝即在寻找解的过程中，预判出从当前状态出发不可能找到解，从而不再从当前状态继续；最优性剪枝就是记录到目前为止找到的最优解，当发现正在探索的解其代价已经不小于最优解，或预测出其最终代价必将不小于最优解，则停止当前解的探索。
Meet the Instructors
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
同学们好，那接下来我们再说一道比较经典的搜索题。
这个题目蛮有诱 惑性啊，叫生日蛋糕。
大家都喜欢过生日、都喜欢吃蛋糕。
这道题目说的是呢，我们要制作一个体积为 Nπ 的这个M 层生日蛋糕。
它的每一层都是一个圆柱体。
假设我们从下往上数的第 i 层 这 i 是大于等于 1，小于等于 M 的。
假设第 i 层蛋糕它是 一个圆柱体，而且这个圆柱体呢，半径为 Ri，高度为 Hi。
当我们这个 i 小于 M 的时候，我们要求 Ri 比 Ri+1 大。
且 Hi 比 Hi+1 大。
也就说这个蛋糕它从下往上
每一层的半径都比上一层的半径大、每一层的高度都比上一层的高度高。
大家牢记这一点，每一层的半径都比上一层半径大、每一层高度都比上一层高度要高。
然后我们做完蛋糕就得在这个蛋糕表面上抹奶油对吧？ 然后为了尽可能节约经费，我们希望蛋糕的外表面，
这个外表面不包括最底下一层的那个底面。
我们希望外表面面积 Q 最小，这样我们就最省钱了。
那我们假设 Q = Sπ。
那要求你写个程序，对给定的 N 和 M 你要求出这个蛋糕的制作方案。
也就说每一层的 Ri 和 Hi 的值你都给它求出来，然后我们使得这个 S 最小。
然后我们这题目里面除了这个 Q 以外呢，所有的数据都是正整数。
额，那我觉得这个题目出的不大好。
主要是它说是为了省钱所以才要
这个这个外表面积最小，我觉得把它改成为了减肥，少抹点奶油，这题目就更好了。
好，总而言之吧，那我们这个题目里面牵扯到的体积和面积都是 Nπ 什么 Sπ。
那这样的话，以后我们在程序里面的时候，
在说到面积和体积的时候，我直接就把π这个系数就去掉了，就不考虑π这个系数了。这样就
更简单一些。
那我们当然拿到这个题目第一感觉就是我要做深度优先搜索，这个是没错的。
那深度优先搜索的时候，怎么搜索呢？ 那我 们就枚举每一层可能的高度和半径。
这个是最暴力的办法了，对吧？ 这个大家都想得到。但问题是，如果你这么做的话， 指定是需要超时的。
那我们说，深度优先搜索我们不想超时， 那我们要从哪几个方面去努力呢？ 第一点。
我们要讲究这个，要考虑好搜索的范围。
你不要把搜索的范围盲目的扩大，对吧？ 搜索范围能缩到多小就缩到多小。
这是第一点。
第二点呢，就要考虑这个搜索的顺序。
那在咱们这个题目里面，这个搜索的范围到底怎么确定呢？ 就是我们要枚举每一层可能的高度和半径。
那这个可能的高度和半径，它就总得有个上限吧。
你不能说高度和半径从大或者从几十亿什么开始枚举，那肯定是不妥的，对吧？ 这每一层的高度和半径肯定得有一个上限。
那这个上限如何确定呢？ 那我们知道高度和半径的， 高度和半径最大的那一层就是底层。
所以呢，在给定蛋糕总体积的情况下，我们能够推算出一个最底层 蛋糕它的半径和高度的上限。
注意这个是上限，并不意味着最底层的半径和高度就能达到那个上限。
它也许根 本就达不到它差得好远，但我们好歹可以算出一个上限。
对吧？起码你可以用什么最底层的体积不能 超过蛋糕的总体积来推算它的高度和半径的上限，对吧？
当然你这 样算出来可能这个上限还有点儿大。
我们等会在程序里面看到我们怎么样把这个上限尽可能缩小。
好，这个就是，搜索范围的这个问题。
下面我们再说这个搜索顺序的问题。
就是我们尝试搭这个蛋糕的时候，我们可以从上往下尝试。
就先是最顶层，枚举最顶层的那个， 那个高度和半径。
搭完最顶层了我们再搭这个 从上往下数的第二层，枚举它的高度和半径。这从上往下搭是一个办法。还有一个办法呢就是-
从下往上搭。我们先 枚举最底层的那个蛋糕的高度和半径，去假设了一个最底层的高度和半径以后呢我们再去试。
最底层的上面那一层的高度和半径，啊，从下往上，这也是一个顺序。
那同学们觉得从下往上好还是从上往下好呢？ 这里面就用到我们前面所说的一个搜索的顺序的基本原则。
就是一个事情如果分成好几个步骤来完成的话， 那我们要去先尝试可能性少的那个步骤。
那我们搭蛋糕不是有M层吗？ 那就是说我们 这个搭蛋糕的这个事情可以分成M个步骤来完成。
那么从下往上和从上往下， 是两种顺序。
那我们到底 该怎么做呢？ 我们说了我们要先尝试可能性小的那个， 可能性少的那个步骤。
那， 最底层的可能性少还是
最顶层的可能性少呢？ 因为最底层的体积大， 这基本上很明显，就是最底层的
可能性要比最顶层的可能性要少。
所以我们，每一层的体积和半径 的值可能越大它的可能就越少。
所以我们要从下往上搭。
这就是一个搜索顺序的问题。
那么还有一问题呢就是 我们在对同一层的蛋糕进行尝试的时候，我们要枚举它的高度和半径。
那我们枚举高度和半径的时候，我们是从大枚举到
小，还是从小枚举到大呢？ 这同样道理，我们应该从大 枚举到小。
就是我们尝试高度和半径的时候，先试大的再试小的。
就是我们在确定了搜索范 围，就是底层蛋糕最大可能半径和最大可能高度以后，我们要确定这个搜索顺序。
搜索顺序呢就是要，从底层往上搭蛋糕，而不是从顶层往下搭。
而且在同一层进行尝试的时候， 半径和高度都是从大到小去试。
那么， 这几个问题搜索范围、搜索顺序这个问题解决以后，
够了吗？ 当然这还没算完。这要算完了话在这个题就不是经典题，而是水题了。
我说完这句话我都觉得很穿越，因为上半句话是好几天前说的，你看我这个衣服都变了。
Ok好吧，那现在我们要做这个深度优先搜索题，我们一定要想到一点是什么？ 一个法宝，就是剪枝。
那什么叫剪枝呢？ 剪枝就是说要及早判断出
当前这个情况往下做已经没有希望，不可能找到最优解了， 或者连解都找不到了，那我就停止当前正在探索的这个解。
这个叫做剪枝。
这样能够避免很多无谓的这个搜索。
那具体到这道题目我们如何进行剪枝呢？
那么说到剪枝，首先你就要想到的一种剪枝就是能够适用于所有的深度优先搜索的。
这种剪枝，我们可以称之为叫做，这个这个， 最优化剪枝。
它的基本思想就是 我程序会记录到目前为止找到的那个最优解。
然后我当前在探索一个解的时候如果我发现 我当前这个解所花的代价都已经超过了那个最优解
的代价了，就到目前为止最优解的代价了。
那我当前这个解就没有必要再探索下去了。
啊，这个就是最优化剪枝。
那我们这道题目当然可以用最优化剪枝啦，就是我们搭蛋糕， 从底层往上搭。
我们在搭建的过程中如果我们发现现在已经搭好的部分 它的这个表面积都已经超过了到目前为止我们
已经求得的那个最优解的那个最优蛋糕的表面积的 数量，那么我们当前这个蛋糕就可以停止搭建。
啊，这就叫做最优化剪枝。
这个剪枝我们叫它剪枝1。
那还有一种剪枝 是什么样的剪枝呢？ 除了最优化剪枝以外，还有一种特别常用的剪枝我们称之为 这个叫做可行性剪枝。
什么叫可行性剪枝啊？就是说你正在探索 一个解，你探索到一半的时候发现再做下去
根本就没有希望能够求得解，那我马上就不要再做了。
这个就叫做可行性剪枝。
可行性剪枝的本质就是说，我及早发现我这么做下去是没有希望的不可行的，那我就不要再做- 下去了。
这叫可行性剪枝。
那具体到咱们这个题目， 都有哪些可行性剪枝可以想呢？
当然有一条，大家可以先想想啊。
好。
有一条就是，我们在搭建的过程中有时候我们可以预见到， 你再往上搭，那么上面那些蛋糕它的
高度已经无法安排，或者半径已经无法安排，这个时候我们就停止搭建。
什么叫高度无法安排啊？ 因为我们知道每一层的高度，
每上去一层它的高度都要比下一层要至少要减掉 1 对吧？
那比方说，像上面还有 n 层需要搭，
然后你现在底层的高度 不到这个灯了，那你每一层高度都要减掉1，那你减到最顶层的时候高度都成了负数或者-
是0了， 那就叫不可行，对吧？这就是我们所说的高度已经无法安排，
那这个题目里面还同样存在半径无法安排的情况。因为越往上 每一层的半径都至少要比上一层要减少1，
如果你现在这个底层的半径已经挺小了，你每一层减少1，到最顶层半径都减成0或者负数了- 。那也就 不可行了，对吧？所以这个
搭建过程中遇见到再往上搭，高度或者半径无法安排，我就停止搭建，这个就是剪枝2，它是- 一种可行性剪枝。
那同学们还能不能想出一些其他的可行性剪枝呢，想一想？
实际上还有可行性剪枝， 第一条再来一条可行性剪枝就是，如果我们搭建的过程中
发现还没有搭的那些层的体积， 它一定会超过我们当前这个蛋糕还缺的体积，那我们也可以停止搭建。
什么叫还缺的体积？就是底下我已经搭若干层了这有一个体积，然后我这个蛋糕总体积是确定-
的对吧？ 然后把总体积减去我已经搭好的部分，剩下的部分就叫做还缺的体积
那我就有可能搭着搭着我发现我还有上面若干层没搭
我把上面若干层都给它搭好的话，上面若干层的体积它一定会超过我还缺的体积
那我这个搭法就没法成立了对吧？因为你还剩下那些层 它的体积会有个最小值，比如说它最顶层的半径是1，高度是1对吧？那么再往下数
它体积越来越大，总体积可能就超过了你还缺的体积，那你就不能再搭了 这是另外一个可行性剪枝。
同理还有剪枝4也是一个可行性剪枝一般就是 你在搭建的过程中，如果你发现还没搭的那么层的体积
它最大也到不了你还缺的体积，那你也可以停止搭建对不对？ 所以我们看到在这个问题里面有四种剪枝方案
实际上第一种剪枝方案叫做最优化剪枝，另外三种都是可行性剪枝。
好现在我们来看看这个程序是怎么写的，首先来一个全局变量N，M
它代表是我们要搭一个体积为N的蛋糕，这个蛋糕一共有M层，
然后我这里有一个全局变量minArea， 给它附一个很大的值，这个代表我们
整个问题的最优解，它的表面积，就是那个最小表面积， 然后还有一个全局变量area，初始值是0，
这个东西是代表我正在搭建中的那个蛋糕现在已经搭成的那个表面积， 然后我们还会有一个minV[30]，
因为我们这个层数最多是30， minV[30]，请问这个minV[n]它就表示n层蛋糕
至少会有多大，minV[n]表示n层蛋糕的最小体积，
那么这个minA[n]表示
n层蛋糕最少的侧表面积 我们只需要考虑侧表面积就行了，因为那些顶面它们总的面积实际上就是
整个蛋糕底面的面积对吧？那个是固定的，所以我们只需要
考虑侧表面积就OK，在底层大小确定的情况下，我们只需要考虑侧表面积就可以了，
然后我们看min里面函数里面怎么写？首先是把蛋糕
M层蛋糕，体积N读进来，然后
minv[0]、minA[0]当然都是等于0对吧？然后
我们在对这个我们要求出这个minV数组和minA数组，
6那我们就一层一层往下看，那么
minV[i]也就是说 i层蛋糕不是说第i层，说的是
一共有i层的那个蛋糕，一共有i层的那个蛋糕它的最小体积是等于多少呢？
当然就是一共有i-1层的蛋糕的那个最小体积再+i*i*i，
为什么要+i*i*i？因为i*i*i实际上就是第i层蛋糕的最小体积，
因为我们第i层蛋糕它的半径至少是i，高度也至少是i对吧？
那个π这个系数我就扔掉不要了，因为我们输出答案的时候也不要再乘以π，
所以我们就说第i层蛋糕它的最小体积是什么？πR2*h，
那里面半径至少是i，高度也至少是i，然后把π扔掉，那么第i层蛋糕的最小体积就是i3。
那我们由minV[i-1]就能够推出minV[i]对吧？
好，那同理我们也去递推这个minA[i]，minA[i]就是什么？是
i层蛋糕，不是第i层了，是一共有i层的那个蛋糕它的最小的那个侧面积，
它的最小侧面积递推关系就是它等于
i-1层的那个蛋糕的最少侧面积再加上第i层蛋糕的最小侧面积对吧？
那第i层蛋糕我们说它半径至少是i，高度至少是i，所以第i层蛋糕
它的最小侧面积就是2*i2，π我们就扔掉不要了。
好，现在我们就求出了所有的minV和minA了，
然后我们直接就可以做一个剪枝了，如果minV[M]>N，
就是什么意思？就是M层蛋糕它最小的体积 都比你想要做的那个体积N要大的话，那我们就知道这个问题是无解的对吧？
无解的话就按题目要求直接输出0就OK了，这就是第一个剪枝了， 它是一种可行性剪枝是吧？
接着往下看，然后 按照我们刚才前面说了一大堆，我们得首先确定一个搜索的顺序，
搜索的范围然后再确定一个搜索的顺序对吧？那我们先解决搜索范围的问题
这个搜索的范围指的就是最底层的那个蛋糕 它的半径的上限以及
它的高度的上限，那我们先求一个最底层蛋糕它的高度的上限，我们记为maxH，
最底层蛋糕它高度的上限是什么呢？ 那我们知道整个蛋糕的体积是N，
然后蛋糕一共有M层 那么上面M-1层蛋糕它的最少的体积是什么？
是这个minV[M-1]？那么 最底蛋糕它的体积
最大就是N-minV[m-1]，是吧？这是最底层
体积最大值，而且我们知道最底层蛋糕它的半径至少是M，
因为你就算最顶层蛋糕它的半径是1，那每一层半径加1到了最底层
也就是第M层，它的半径至少是M。那 我们把这个最大可能体积再给它除以
最少可能半径的平方，那除出来
它就是底层最大可能的高度对吧？但你这个除出来有可能是个小数，
那准确的只有可能是小数，但你在这里是做两个整数的运算， 所以算出来是个整数，说不定就少了个尾巴，所以我干脆再给它加1，这样才准确，
这个就是求出了maxH，就是最底层蛋糕它的最大可能高度。
那在接下来我们还需要去求最底层蛋糕的最大可能半径，
也就是这个maxR，那它求的道理也是一样的， 就是说我们有了这个最底层
蛋糕它的最大体积就是N-minV[m-1]是吧？
然后我们有最大体积，然后我们知道最底层蛋糕它的高度至少是M，
那我们当然就可以求出最底层蛋糕它的 最大半径可能是什么了，就是这个最大体积
除以最小高度，然后我们再开平方，
开平方结果有可能是小数对吧？那我们
这里的maxR是个整数，所以我就在这里再加一个1，这样就不会把小数部分扔掉，导致范围
变得比实际的要小了。好，现在我们求出了这个搜索范围就是底层
蛋糕它的最大可能高度和最大可能半径。
那接下来我们就要去，用深度优先的办法去
搭建这个蛋糕了，就是从底向上去搭建，那我们正在搭建中的这个蛋糕
它的面积，表面积是0，
然后我们这个全局变量叫最优解，一开始是一个很大的数，
现在我们就用这个深度优先搜索去搭这个蛋糕了， 这Dfs函数它就代表我开始搭蛋糕，它的具体含义就是
我要搭一个体积为N，乘数为M的蛋糕， 然后这个蛋糕它的底层最大半径是maxR，
底层最大高度是maxH，这就是这个Dfs含义，这个函数的含义。
那么在搭建蛋糕的过程中有可能搭建成功了，那它就把搭建成的那个蛋糕的
面积跟这个minArea去比较一下，如果它比minArea 要小的话我们就更新minArea对吧？好，那现在这个。
这就是搭蛋糕蛋糕搭完了，我们发现minArea 还是它原来的值，那就说明我们搭蛋糕根本就没搭成，因此我们就输出0。
如果minArea被更新了，那我们就输出minArea，这就OK了。
好，接下来我们再看看关键的Dfs函数到底怎么写，深度优先搜索函数， Dfs（int v,
int n, int r, int h）这个函数的含义就是： 我需要搭一个n层的蛋糕，这个n层蛋糕它们的体积凑起来正好就是v，
然后这个n层蛋糕的底层半径最大是r， 底层高度最高是h。那
它是一个递归函数，它肯定有一些边界条件，终止条件，终止条件是什么呢？
如果n=0，那就说明什么？我没什么可搭了， 没什么可搭了，但这个时候如果v不等于0，那就说明什么？
你接下来就不可能再凑到v这个体积了，就意味着搭建失败，所以我们就返回了。
那如果n=0，v=0，那就说明什么？正好搭成了，对吧？
我们该凑的体积都已经凑齐了，然后也没有更多程序要搭了，那就说明我这个蛋糕完成了。
蛋糕完成了，那么这个时候我们刚刚搭好了这个蛋糕，它的面积会是area。
而我们到目前为止找到的那个最佳蛋糕，它的面积是minArea，
那我当然就要比较一下minArea和这个area，就有可能更新这个minArea了。
然后就return，这是搭成一个蛋糕的这个情况。
那么我们看，如果n不等于0，那说明蛋糕仍在搭建中，n不等于0，结果我们发现v就已经- 小于等于0了，
那说明蛋糕仍在搭建中，n不等于0，结果我们发现v就已经小于等于0了，
就是说你已经搭建的这部分它的体积 都已经超过了整个蛋糕的体积了，那我们等于搭建就失败，也就return了
接下来我们看，如果我们发现minV[n]大于v，
minV[n]是什么意思？就是n层蛋糕
最少的体积，如果我们发现n层蛋糕最少的体积都比你这个v要大，
那说明我们根本就不可能搭出这样一个n层蛋糕出来，对吧？ 那我们就return，就搭建失败。当然就是剪枝3了。
再看，如果我们发现area+ minA[n]，
area是什么？就是当前正在搭的这个蛋糕，
它已经搭好的部分，那已经搭好的部分当然就是第n+1层，第n+2层，反正就是第n层下- 面的那些东西，对吧？
area代表已经搭好的这个部分。已经搭好的这个部分 它的面积是area，然后这个minA[n]是什么呢？
minA[n]是n层蛋糕你搭出来的 最小的这个侧面积。
我们这个area已经包含底面的面积了，
所以再接下来往上搭蛋糕的时候，我们只需要考虑侧面积就行了。
那如果n层蛋糕下面那些层 已经搭好的那些部分，它的面积是area，然后剩下的这个n层
你搭起来侧面积至少也会是minA[n]，如果这两项的和
加起来就已经比我们找到的最佳蛋糕它的表面积
还要大，或者是相等的话，那我们当前正在搭建的
这个蛋糕也就没有必要搭下去了，对吧，这就是剪枝1，所以如果我们发现这个条件成立，我- 们就return。
这个是叫做最优化剪枝。接下来我们还看到一个可行性剪枝，
这就是剪枝2，它说的是什么？就是h<n或者r<n， h
<n意味着什么？就是我第n层蛋糕 它的高度h都比n小了，那你可以想象你往上搭，每一层的
高度都要减少1，那么到最顶层的时候，高度就变成0或者比0还小，对吧？ 同样半径也有这样一个问题，所以
这个条件要是满足实际上就等于是我们在剪枝2里面所说的， 再往上搭的时候，高度和半径都已经没法安排了，那我们搭建肯定就会失败，所以就会ret-
urn， 这就是剪枝2。还有剪枝是吧？
还有一个最强的剪枝，是这个剪枝4，这个剪枝4， 没有的话你整个程序5秒都超时，在pog（音）上面，有的话呢，
10ms就能过。看来这个剪枝是最强的。当然哪一个剪枝最强 往往跟数据是怎么生成的有关系，对吧？
好，那现在这剪枝4说的是什么？就是MaxVforNRH(n,r,h)<v，
这个说的是什么含义呢？MaxVforNRH(n,r,h)它说的就是，
一个n层蛋糕，它的
底层最大半径是r，底层最大高度是h，那这样的一个n层蛋糕，它的最大体积
我们就把它计成MaxVforNRH(n,r,h)。
n层蛋糕底层最大半径r，底层 最大高度h，这样一个n层蛋糕的最大体积我们计为MaxVforNRH(n,r,h)。
如果这样一个体积它是小于v的， 那说明你再接着往上搭就没有意义了。对吧，我们整个Dfs说是要搭一个
n层的蛋糕，然后它的体积是v。那你现在算出来它的体积
最大也不会达到v，那我们这个蛋糕就没什么好搭下去了，所以就return，这就是- 剪枝4。
那我们的程序如果越过了上面的所有的剪枝方案， 那这个时候就说明当前这个蛋糕还有必要尝试下去，
你就认认真真的去搭这个蛋糕。那怎么搭呢？我们从 底往上搭，对吧？那我们当然就先搭
最底下的那一层，对吧？最底下那一层我们要搭的时候，我们就枚举它的
半径和它的高度，那我们就先枚举半径好了，是吧？
那我们枚举半径的时候，我们到底是从小枚举到大，还是从大枚举到小呢？
按照我们前面所直观的想法，先选择步骤少的
那个步骤的思路，我们应该是从大到小的去枚举这个半径。
那这个底层蛋糕它的半径最大是r，
最小是什么？最小当然就是n，底层半径 最大是r，最小是n，所以我们枚举这个半径rr，让它从r
一直走到n。这是在枚举
半径。好了，如果
n=M，说明什么问题？就是我们正在尝试的
这一层蛋糕，就是
整个蛋糕的最底下一层，这种情况下，就意味这我们刚刚开始搭建一个蛋糕，
那这个时候我们就要把正在搭建的这个蛋糕的面积area初始化成
rr的平方，这个rr的平方是什么？就是最底层的
蛋糕它的底面积，对吧？我们知道整个蛋糕它的表面积
是由每一层蛋糕的侧面积再加上每一层蛋糕的水平面的面积组成的，
那么每一层蛋糕的水平面我们都给它投影到 蛋糕的底部，那每一层蛋糕的水平面的面积加起来正好就是
最底层蛋糕的底面积，对吧？那最底层蛋糕的底面积就是这个rr平方。所以我们在
刚刚开始搭建一个蛋糕的时候，我们把蛋糕的面积就初始化成
最底层蛋糕的底面积了。好，接下来我们 来枚举第n层蛋糕它的高度。
第n层蛋糕它的高度最大是h，最小就是n，我们枚举 高度的时候同样也是要按照从大到小的顺序来进行枚举的。
现在我们进到这个循环，就确定了第n层蛋糕的
半径是rr，高度是hh，那第n层蛋糕它的
侧面积是多少呢？当然就是2×rr×hh，然后我们把这个侧面积给它加到area上面去。
这个时候我们就完成了第n层蛋糕的
尝试。那接下来我们就要去往上去搭
第n-1层n-2层一直往上搭了，对吧？所以这时候我们递归调用Dfs
进行后续的搭建。后续搭建的时候我们 要凑的体积v就要减少了，对吧？就要减掉第n层蛋糕的体积，
第n层蛋糕的体积是什么呢？就是rr的平方再乘以hh。我们再往上搭，
剩下的体积就是v减少去rr平方乘以hh，对吧？
然后再往上搭的话，我们要搭的蛋糕就是n-1层的蛋糕了，对吧？那么
这个n-1层蛋糕它的底层最大半径是多少？当然就是第n层蛋糕的
半径值减1，那上面那个n-1层蛋糕，它的底层最大高度自然就是
当前第n层蛋糕的高度减1。所以我们就写出这个 递归的式子去搭建上面的那个n-1层蛋糕。
那当然我们搭建完了以后，我们还给把这个area
恢复到原来的这个值，对吧？这就相当于是一种回溯。我们这个Dfs是一种搭建的
方案，那我们可以用别的搭建方案，如果你要尝试别的搭建方案的话，那么你这个are- a当然得
恢复成原来的值，你才能够再继续尝试别的方案，对吧？好，我们这整个
递归的Dfs就做完了。下面我们就要回过头来看看这个 MaxVforNRH(n,r,h)到底是怎么写的？当然这个很容易，
MaxVforNRH(n,r,h)说的就是， 我要搭一个n层的蛋糕，这个n层的蛋糕它的底层
最大半径是r，最大高度是h，就问你这个n层的蛋糕最大体积是多少？
那很好算啊，你就每一层的半径和高度
都往最大去算，对吧？第n层蛋糕它的最大半径是r，高度是h，
那第n-1层蛋糕它的最大半径就是r-1，高度就是h-1，于是我们就让i
从0一直走到n-1，一开始的体积是v，然后我们这个v就+=每一层的最大体积，
就是（r-i）×（r-i）×（h-i），对吧？整个循环走完我们就求出了这个所谓的
最大体积了。那么这个题目就是这样，确实比较经典，我们在这里面看到了
两种剪枝方式的应用，一个当然就是 最优化剪枝，还有另外一个就是
可行性剪枝，而且这个题目里面可行性剪枝出现了好多处，大家牢牢记住，
做伸收的时候，考虑剪枝先想最优化剪枝，再想可行性剪枝。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
