《递归习题分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《递归习题分析ppt课件.ppt（42页珍藏版）》请在三一办公上搜索。
1、,Services,分析与求解,递归问题,Services,分析与求解,递归问题,递归的定义,一个过程或函数在其定义或说明中直接或间接调用自身的一种方法把一个大型复杂的问题层层的转换成一个与原问题相似的规模较小的问题来求解,优点,少量的程序就可以描述出解体过程所需要的重复计算大大减少了程序的代码量,缺点,运行效率较低,见递归的定义,Services,分析与求解,递归问题,递归问题的分析步骤,考虑问题规模在初始情况下的求解初始情况通常情况下是已经条件或者可以通过非递归求解的函数,考虑问题规模向较小规模的发展子问题的性质和原问题具有相同的性质，只是规模上比原问题有所缩小处理如何将子问题的解集合处理
2、得到原问题的解常常是约束使用递规思维的瓶颈,Services,分析与求解,递归问题,递归必须要有基本条件,f(n) = f(n-1) + f(n-2),递归必须朝基本条件运行,f(0) = 0f(n) = f(n/3+1) + n 1;,long function(int N) if(N=0) return 0; if(N1) return function(N/3+1);,long function(int N) return (function(N-1)+function(N-2);,递归问题的基本原则,分析与求解,递归问题,推理方法,归纳推理：从特殊归纳出普遍特殊：所有观察到的乌鸦都是黑
3、色的普遍：所有乌鸦都是黑色的,演绎推理：从前提的已知的事实，“必然的”得出的推理前提1：所有公乌鸦都是黑色的，所有母乌鸦都是黑色的前提2：乌鸦要么是公的，要么是母的结论：所有乌鸦都是黑色,基于公理的演绎推理总是正确的归纳推理在演绎上通常是无效的归纳是开放的，但是演绎是封闭的“对所有事情都坚持可靠的演绎上的正当有理的人会饿死 ” 大卫.休谟,分析与求解,递归问题,数学归纳方法,数学归纳法的定义证明当n等于任意一个自然数时，某命题成立。证明当n=1时，命题成立假设当n=m, m为任意自然数时命题成立，推导出n=m+1时命题也成立注意，这里的推导必须是演绎推理方法。,数学归纳法的变体从0以外的数字开
4、始只针对偶数或者奇数递降归纳法,超限归纳法将数学归纳法的第2步改成：假设当nm，m为任意自然数时命题成立，推导出n = m时命题也成立,分析与求解,递归问题,更一般的归纳法*,良基关系对于类X上一个二元关系R被称为是良基的，当且仅当所有X的非空子集都有一个R-极小元，就是说对于X的每一个非空子集S，都存在一个S中的元素m使得对于所有S中的s，二元组(s, m)都不在R中,数学归纳法是良机归纳法的一种特殊情况0是自然数集合上后继关系的一个极小元，因此只需要证明对于n=0，命题成立(m, m+1)属于后继关系，因此假设n=m成立的时候，只需要证明n=m+1的时候也成立,分析与求解,递归问题,利用数
5、学归纳思想求解递规问题,最简单的数学归纳关系已知一个数组,对一个数组进行求和,解法,循环解法，依次遍历数组，求和，演绎推理思维,int Sum_Loop(int* array, int array_size) int sum = 0; for(int i = 0; i array_size; i+) sum += arrayi; return sum;,递规解法，假设前n-1项已经知道，那么加上第n项的值那么就是前n项的求和，归纳推理思想,int Sum_Recursion(int* array, int array_index) if(array_index = 0) return arra
6、y0; else return arrayarray_index + Sum_Recursion(array, array_index 1);,分析与求解,递归问题,1063斐波那契数列,描述,第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 = a = 20),菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。 给出一个正整数a，要求菲波那契数列中第a个数是多少。,输出,n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数的大小,输入,long function(int N) if(N = 1
7、 | N = 2) return 1; return (function(N-1)+function(N-2);,分析与求解,递归问题,1063斐波那契数列,解题思路,按照斐波那契数列的定义，对于每个输入调用计算的递归函数返回结果,主要问题,输入输出格式不对没有使用递归程序实现,分析与求解,递归问题,数学归纳关系适用场景,存在规模为n的问题和规模小于n的问题的映射，利用数学归纳法的思维去求解。,数学归纳关系求解过程,1. 确定问题规模。问题规模来自于原始问题中的各种变量，问题规模通常应该可以量化的表达，并且对于问题求解没有本质上的变化。2. 寻找初始条件初始条件通常是问题规模的特殊情况或者极端
8、化。在这种条件下这个问题应该足够简单。寻找初始条件和问题规模常常是一起考虑的。3. 归纳解决简单的归纳方法主要有两种：假设我们已经得到了问题规模为n-1的解决方案，针对这个解决方案考虑如何变换到问题规模为n的方案。（直接后继归纳）假设我们已经得到了所有问题规模小于n的解决方案，考虑问题规模为n的问题如何适用前面较小问题规模的来进行求解。（超限归纳）,分析与求解,递归问题,猴子分苹果（单维上的直接后继归纳关系）,描述,输入猴子数目n 和扔掉的个数 k，其中 k 小于 n，n 和 k 之间以空格间隔。,有1堆苹果共 m 个，由 n 只猴子按个数平均分配。每次到达苹果堆放地的猴子只有1只，而且每个猴
9、子都会平均分 1 次苹果。第1个到达的猴子将苹果平均分成 n 等份，但发现多 k ( k n )个，于是，将多余的k个扔掉，然后拿走其中的1等份。第 2 个猴子同样将剩余的苹果又分成 n 等份，也发现多 k 个，并同样将多余的 k 个扔掉，然后拿走其中1等份。之后的每个猴子都这样（将剩余的苹果又分成 n 等份，也发现多 k 个，并将多余的 k 个扔掉，然后拿走其中1等份）。假设最后的猴子分配后至少可以拿走1个苹果，请根据输入的 n 和 k值，计算最小的 m,输出,输出最小苹果数目,输入,分析与求解,递归问题,猴子分苹果（单维上的直接后继归纳关系）,解题思路,寻找初始条件要想苹果总数最少，那么最
10、后一个猴子正好拿走1个苹果，需要求出第1个猴子取苹果时候的总数，因此这个问题的“规模”与猴子取苹果的序号i有关，用a(i)表示第i个猴子取苹果时候的总数，于是a(n) = n+k寻找归纳关系第i个猴子取的时候总数为a(i)，则第i+1个猴子取得时候总数为a(i+1) = a(i)-k-(a(i)-k)/n由于我们的基本条件是a(n)，我们需要由a(i+1)推导出a(i)才是向基本条件出发。于是根据1可以得到：a(i) = n*a(i+1)/k + k。,主要问题,输入输出格式不对没有使用递归程序实现结束条件没有搞清楚中间递推过程错误,long function(int N) if(N = La
11、stMonkeyNumber) return TotalMonkeyNumber + k; return TotalMonkeyNumber*function(N+1)/k + k;,分析与求解,递归问题,汉诺塔（单维上的直接后继归纳关系）,描述,输入数据只有一个正整数 n (n = 16) ， 表示开始时铁针 A 上的圆盘数。,略,输出,要求输出步数最少的搬动方案，方案是由若干个步骤构成的，输出的每行就表示一个移动步骤，例如，“A-B”就表示把铁针 A 最上层的一个圆盘移动到 B 上。,输入,分析与求解,递归问题,汉诺塔（单维上的直接后继归纳关系）,解题思路,寻找初始条件汉诺塔中可以作为规模
12、的变量是盘子的数目。当盘子为1的时候的情况十分的简单，我们将其作为初始条件，用move(i, p, q)表示将i个盘子从p移动到q。move(1, p, q)就是p-q。(p, q = A, B, C)寻找归纳关系先看看i = 2时,move(2, A, C)的动作：move(1, A, B), A-C, move(1, B, C);我们假设已经“一次性”将n-1个盘子在柱子之间移动的方案已经得到，那么移动n个盘子的问题，就和i=2的时候情况非常相似了: move(n-1, A, B), A-C, move(n-1, B, C),输入输出格式不对依样画葫芦，移动的参数不对,主要问题,思考题,尝
13、试利用数学归纳法证明这样移动的方案的确是最优的，也就是移动次数是最少的。如果n是偶数，每次可以移动2个盘子，那么移动的方案又是如何？如果每次移动的盘子数目不超过k(从1到k之间的一个数字)，那么移动的方案又是如何？如果柱子的数目不是固定的3，而是m，那么如何移动盘子？,分析与求解,递归问题,寻找最长公共子序列（多维上的直接后继归纳关系）已经两个数组a和b，子序列S如果既出现在a中，也出现在b中，那么S称为a和b的公共子序列。给定两个数组求解他们的最长的公共子序列的长度。如1, 3是序列1, 2, 3和1, 3, 5的最长公共子序列。,分析寻找初始条件初始条件只能从已经知道的条件中获取，题目中出
14、现的“规模” 有两个：a的长度和b的长度。那么最简单的，如果a的长度为1并且b的长度为1，那么可以知道最长公共子序列为1或者0。问题的规模是数组的长度，那么就要考虑数组的长度比M和N小的情况，一个最直接的想法是考虑a的前i(iM)个数字和b的前j(jN)个数字组成的序列。我们用L(i, j)表示我们得到的a的前i项和b 的前j项的公共子序列的长度，那么L(0, 0) = IsSame(a0, b0);寻找归纳关系设a的长度为M, b的长度为N，考虑以下问题：如何缩小问题的规模：问题的规模是a的长度i和b的长度j，那么对于L(i, j)的问题，我们可以考虑L(i-1, j)和L(i, j-1)以
15、及L(i-1, j-1)。其中L(i-1, j) = L(i-1, j-1) + 1，L(i, j-1) = L(i-1, j-1) + 1。如何通过子问题得到原始问题的解：我们假设已经得到L(i-1, j), L(i, j-1)和L(i-1, j-1)。 a) 如果ai和bj相等，那么L(i, j) = L(i-1, j-1) + 1。 b) 如果不相等，那么ai和bj不可能同时出现在公共子序列中，所以要么ai出现，此时L(i, j) = L(i, j-1),否则bj出现，此时L(i, j) = L(i-1, j)。到底ai出现还是bj出现，取决于两者的较大值。因此L(i, j) = max
16、(L(i-1, j), L(i, j-1),分析与求解,递归问题,前继求和（单维上的超限归纳关系）f(n) = f(n-1) + f(n-2) + + f(0),描述,输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。,把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法（用K表示）？,输出,输出为一行，表达式的值。,输入,放苹果问题（多维上的超限归纳关系）,分析与求解,递归问题,放苹果问题（多维上的超限归纳关系）,解题思路,寻找初始条件这个问题中的问题规模取决于两个方面，一个是盘子的数目，一个是苹果的总数。我们将M个苹果放在1个盘子和1个苹果放在N
17、个盘子的方案都很容易。我们用f(i, j)表示将i个苹果放在j个盘子的方案数。为了避免重复的方案，我们假定盘子上的苹果数目是递增的（递减也是可以的，这里采用递增的假定）用a(i)表示放在第i个盘子上的数目，则a(0) = a(1) = = a(N)a(0) + a(1) + + a(N) = M利用这些关系我们去尝试减少问题的规模,分析与求解,递归问题,放苹果问题（多维上的超限归纳关系）,解题思路,寻找归纳关系我们依旧试图减少问题的规模1. 首先考虑减少苹果的总数M。如果我们已经在N个盘子上放了M-1个苹果，那么我们如何放最后一个苹果?按照假定，如果我们把这个苹果放在第i个盘子上，那么必须要满
18、足a(i) + 1 = a(i-1) 且 a(i) + 1 = a(i+1)想要确定这样的盘子，那么我们需要保存所有在N个盘子上放置M-1个苹果的方案。,void PlaceApple(int AppleNumber) if(AppleNumber = 1)/如果只放一个苹果，那么一定是把这个苹果放最后一个盘子上 for(int i = 0; i = Solutionsij-1 /产生一个可行方案，保存起来,分析与求解,递归问题,放苹果问题（多维上的超限归纳关系）,解题思路,int PlaceApple(int AppleNumber, int PlateNumber, int limit)
19、if(AppleNumber PlateNumber * limit | PlateNumber = 0) return 0; if(AppleNumber = PlateNumber * limit | PlateNumber = 1) return 1; int sum; for(int i = limit; i AppleNumber/PlateNumber; i+) sum += PlaceApple(AppleNumber - i, PlateNumber 1, i); return sum;,分析与求解,递归问题,放苹果问题（多维上的超限归纳关系）,解题思路,int PlaceAp
20、ple(int AppleNumber, int PlateNumber) if(AppleNumber 0 | PlateNumber = 0) return 0; if(AppleNumber = 1 | AppleNumber = 0 | PlateNumber = 1) return 1; int sum; for(int i = limit; i AppleNumber/PlateNumber; i+) sum += PlaceApple(AppleNumber PlateNumber *i, PlateNumber 1); return sum;,分析与求解,递归问题,放苹果问题（
21、多维上的超限归纳关系）,解题思路,int PlaceApple(int AppleNumber, int PlateNumber) if(AppleNumber 0 | PlateNumber = 0) return 0; if(AppleNumber = 1 | AppleNumber = 0 | PlateNumber = 1) return 1; return PlaceApple(AppleNumber, PlateNumber 1) + PlaceApple(AppleNumber PlateNumber， PlateNumber);,分析与求解,递归问题,数学归纳关系使用小结,1.
22、 问题规模 通常很容易识别。问题规模通常是问题中的某个“数量”，如盘子的个数，数组的长度等。2. 初始条件是对于问题规模的特殊情况的处理初始条件下这个问题一般十分的简单3. 归纳解决的关键是寻找子问题到原始问题之间的转换对于问题规模首先尝试演绎归纳，即假定问题规模n-1已经解决，考虑第n个子问题如果存在多维的问题规模，那么原始问题可能和这多个问题规模上子问题相关如果直接从n-1很难推导出问题规模n的问题，那么尝试超限归纳。考虑从所有问题规模小于n的子问题推导问题规模n的原始问题演绎归纳实际上是超限归纳的一种特殊情况。,数学归纳关系局限,一些情况下，我们无法找到可以量化的问题规模或者无法简单的找
23、到初始条件,分析与求解,递归问题,树形递归问题,定义在树上的良基归纳法递归问题可以和一颗树一一对应尽管问题规模无法直接的“数量化”，但是问题直观上总是向问题规模更小的情况发展。如果增加了一定的约束条件之后，问题变成简单的相似的问题，我们就将这个子问题作为原始问题的子节点。在树形递归问题中，初始情况可能有多种情况根据具体的情况判断什么是递归问题的结束条件或者初始条件。一般都是加上一定的约束条件使得问题较为简单树中一个节点和子节点之间的关系也就是递归问题中的关系。任何一个节点都代表了递归问题的一个子问题，解决子节点的方法都和解决整个树的方法是一致的数学归纳关系是树形递归问题的特例单维的数学归纳关系
24、是退化的树线n维的数学归纳关系是n叉树,分析与求解,递归问题,逆波兰表达式（树形递归问题）,描述,输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。,逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ - * /四个。,输出,输出为一行，表达式的值。,输入,分析与求解,递归问题,逆波兰表达式（树形递归问题）,分析,对于表达式 * + 3 4 * 1 2，等同
25、于*(+ 3 4) (* 1 2)，我们必须首先计算+ 3 4和* 1 2之后才可以得到整个表达式的值。每个运算符后面一定跟随着两个子表达式，子表达式可能是数字也可能还是运算。我们总是可以将一个逆波兰表达式转换成一个树。,在这个树中，任何一个子树也都是逆波兰表达式。树的叶节点一定都是数字节点。基于这个树，我们计算这个逆波兰表达式的值：对于叶节点，那它只可能是数字，表达式的值就是这个数字。如果不是叶节点，那么它的值由它的两个子树的值决定，用EXP(node)表示一个逆波兰表达式的值，那么有EXP(node) = EXP(node-LeftChild) OP EXP(node-RightChild
26、), OP是这个节点的运算符如果存在了这样一棵树，那么我们的计算就很容易了。因此问题的关键在于如何建立这么一棵树。建树的过程和计算值的过程是一致的。当我们读取了一个运算符，那么一定存在两个子树，我们首先建立左子树，返回左子树的值，之后建立右子树，返回右子树的值。,* + 3 4 * 1 2,* 1 2,分析与求解,递归问题,逆波兰表达式（树形递归问题）,解题思路,如果输入为一个数，那么表达式的值就为这个数的值如果输入只有一个运算符，比如输入了*,那么后面的输入一定会产生两组值。这两组值可能是直接的数字，比如3和4，那么结果就是3*4。也可能还是表达式比如输入了+ 3 4和 * 1 2，这个时候
27、的值就是(3+4)*(1*2)。而表达式+ 3 4和* 1 2处理和当前表达式的处理是相同的。本质上是利用递归调用对输入构成一个栈的数据结构,主要问题,输入输出格式不对不知道如何判断输入的是运算符还是数字不知道如何递归计算表达式的值，思维局限在如何对一个已经输入的字符串进行处理。,float function() cinstr; switch(str0) case *: return function()*function(); case /: return function()/function(); case +: return function()+function(); case -:
28、 return function()-function(); default: return atof(str); ,分析与求解,递归问题,二叉树（树形递归问题）,描述,输入只有一行，包括两个正整数x和y，这两个正整数都不大于1000。,由正整数1, 2, 3, .组成了一棵无限大的二叉树。对于两个结点x和y，假设他们到根结点的路径分别是(x1, x2, . ,1)和(y1, y2, . ,1)（这里显然有x = x1，y = y1），那么必然存在两个正整数i和j，使得从xi 和 yj开始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,. 现在的问题就
29、是，给定x和y，要求xi（也就是yj）。,输出,输出只有一个正整数xi。,输入,分析与求解,递归问题,二叉树（树形递归问题）,分析,相比于逆波兰表达式，二叉树问题已经有了树的模型，现在需要考虑的是问题的初始条件和子问题的关系。如果这两个数字相同，这两个数字的公共祖先就是自己本身。这就是问题的基本条件。如果这两个数字不相同，我们 “翻族谱”去发现公共祖先。,因此，如果两个节点并不一致，那么我们继续向上寻找使得这两个节点变成相同的节点。问题是我们如何向上寻找？如果这两个节点高度不一致，那么我们只有提升那个“矮”节点才有可能使得两个节点达到一致。如果这两个节点一致，但是并不是一样的节点，那么就一起提
30、升。,分析与求解,递归问题,利用归纳结构解决递归问题,寻找初始条件考虑问题在某些特定情况下的变化寻找归纳关系不管何种归纳方法，都存在着从原始问题向子问题的发展。对于归纳方法的分类只是提供了一种去寻找归纳关系的套路，照着这些套路去思考总会能得到一些启发。如果存在数组或者多个变量的问题，那么尝试减少一个变量的子问题如果存在树或者其他结构，那么尝试着看他们的父节点或者子节点所代表的子问题在得到了子问题的解之后，需要考虑如何组合来得到父节点的解。这个过程有时候比较麻烦，是递归解决问题的关键。,利用递归的常见算法：回溯法：n=n-1分治法： n=n/2,分析与求解,递归问题,回溯递归问题,Bool Ba
31、ckTracking(int n) for each CANDIDATE c about n /对第n步的所有可能解进行枚举，尝试每个可能c MAKE solutionn = c if n = LAST_ELEMENT /如果已经对所有步骤上的解，那么判断是否符合题目中的约束 if(solution IS A COMPLETE SOLUTION) OUTPUT solution return true else return false else if(BackTracking(n+1)/如果c可以到达一个可行解，那么说明c是一个正确尝试 return true; return false;
32、/如果所有的尝试都不能到达可行解，那么说明这个问题不可解,分析与求解,递归问题,回溯递归问题,回溯问题可以转换成为树形递归问题,分析与求解,递归问题,红与黑（回溯递规问题）,描述,包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下 .：黑色的瓷砖 #：白色的瓷砖 ：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次 当在一行中读入的是两个零时，表示输入结束。,有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，
33、只能向相邻的四块瓷砖中的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。,输出,输出为一行，表达式的值。,输入,分析与求解,递归问题,红与黑（回溯递规问题）,分析,如果站在一个黑色的砖上,但是四周都不是黑色的,或者四周都走过了,那么就无法再前进,这个就是问题的基本条件。如果站在其中一块黑砖上，我们尝试的向四周走动，每走一步就增加一步。为了避免重复计数，走过的黑砖被标记不可以再行走。在这个问题中，本质上也是回溯解法，不断的向四周进行尝试的走动，但是这个问题中不发生尝试错误的“修正”。,void WalkAround(int x, int y) if(Bricksij = RED
34、| Visitedij = true) return; TotalVistedNumber+;/走到了一个新的黑砖上，标记这个黑砖已经被访问，并且增加计数 Visitedij = true; /向四周走动 WalkAround(x-1, y); WalkAround(x+1, y); WalkAround(x, y+1); WalkAround(x, y-1);,分析与求解,递归问题,红与黑（回溯递规问题）,分析与求解,递归问题,分解因数（回溯递规问题）,描述,第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (1 a 32768)。,给出一个正整数a，要求分解
35、成若干个正整数的乘积，即a = a1 * a2 * a3 * . * an，并且1 a1 = a2 = a3 = . = an，问这样的分解的种数有多少。注意到a = a也是一种分解。,输出,n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数。,输入,分析与求解,递归问题,分解因数（回溯递规问题）,分析,如果这个数a是一个素数，那么肯定不能够再进行分解了。分解的情况只有一种。如果这个数a可以被分解，如果a = a1*a2*ai ，我们利用回溯的方法去枚举每个ai的可能。值得注意的是，如果我们对a分解的第一个因数是a1的时候，那么ai(i1)分解的因数都必须大于a1。,vo
36、id function(int x, int limit) if(x = limit) function(x/i, i);,分析与求解,递归问题,分解因数（回溯递规问题）,(30,1),(15,2),(10,3),(5,3),(3,5),(5,2),(2,5),(6,5),(3,2),(2,3),2,3,5,分析与求解,递归问题,分治递归问题,DivideAndMerge(int array) /将原问题的输入划分成子问题的输入 for(int i = 0; i PARTITION_NUMBER; i+ sub_arrayi = Partition(array, i); /调用相同的过程来获取
37、每个子问题的解 for(int i = 0; I PARTITION_NUMBER; i+) sub_solutioni = DivideAndMerge(sub_arrayi); /将子问题的解合并起来得到这个问题的解 return Merge(sub_solution);,问题可以分解成为若干个相互独立的子问题原问题的解是这些子问题的解的合并分治递归问题可以自然的转换成树形递归问题,分析与求解,递归问题,石子归并（分治递规问题）,描述,第一行为石子堆数 N；第二行为每堆石子数，数字之间用一个空格分隔。,现摆一排 N 堆石子（N 100），要将石子有次序地合并成一堆。规定每次只能选取相邻的两
38、堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。编一程序，由文件读入堆数N及每堆的石子数（ 20）。选择一种合并石子的方案，使所做 N1 次合并，得分的总和最小。,输出,最小的得分总和。,输入,分析与求解,递归问题,石子归并（分治递规问题）,分析,对于一堆石子10, 2, 3，分析石子堆的合并是如何发生的,27,3,2,10,12,20,3,2,10,5,分析与求解,递归问题,总结,递归的归纳类型数学归纳法：直接后继归纳和超限归纳良基归纳法：树形归纳应用递归的算法回溯：问题是一步步的解决，每一步的解都影响后面的解分治：问题总是可以分成多个部分，而每个部分的解决是相互独立的不要陷入思维陷阱想的太复杂：过分注重一些细节，实际上许多细节是交由子问题去解决想的太简单：受困于“线性”的思维，实际上许多问题是“树形”的,多做题，多思考举一反三，题目有很多，但是类型很有限对于题目多去思考，80%的时间应该花费在纸和笔上，而不是坐在电脑前面发呆提高编码能力，代码应该能够直接表达你的思维,
