在真实世界中，为了提升效率，我们希望一直更进一步提升效率，比如提升工程进度，最优的调度方案，地图中的最短路径，得到最大的收益，最短的行车路线等等。这类诉求对我们的生活也会有非常大的影响，今天我们重点介绍关于最优解相关的算法。
说道最优解相关算法，核心是递归思想、贪心算法、分治算法、动态规划思想思想。今天重点摘录核心是上面的算法思想案例。
个人认为：其中贪心、分治、动态规划，都会用到一部分递归思想，是递归思想的一种算法思想的延展。
同时本文还将摘选关于回溯和分支界限的算法思想。
首先我们看下这三种算法思想的定义：
、递归法
程序调用自身的编程技巧称为递归（cursion）。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
注意：
()递归就是在过程或函数里调用自身;
()在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
、贪心算法
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。
用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
贪婪算法是一种改进了的分级处理方法，其核心是根据题意选取一种量度标准，然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量，如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。
、分治法
分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治法所能解决的问题一般具有以下几个特征：
()该问题的规模缩小到一定的程度就可以容易地解决；
()该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
()利用该问题分解出的子问题的解可以合并为该问题的解；
(4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
4、动态规划法
动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。
5、回溯法
回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
其基本思想是，在包含问题的所有解的解空间树中，按照深度优先搜索的策略，
从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，
如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。
（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，
且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，
只要搜索到问题的一个解就可以结束。
6、分支界限法
分枝界限法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。
分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。
该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），
并为每个子集内的解的值计算一个下界或上界（称为定界）。
在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支，这样，
解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。
这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。
因此这种算法一般可以求得最优解。
与贪心算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，
所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，
都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，
可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝）。
一、递归算法案例：
经典汉诺塔问题分析问题来源：汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从上往下从小到大顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘，只能移动在最顶端的圆盘。有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩，当然这个传说并不可信，如今汉诺塔更多的是作为一个玩具存在。
现在有n个圆盘从上往下从小到大叠在第一根柱子上，要把这些圆盘全部移动到第三根柱子要怎么移动呢？请找出需要步骤数最少的方案
因此我们可以将问题简化描述为：n个盘子和根柱子：A(源)、B(备用)、C(目的)，盘子的大小不同且中间有一孔，可以将盘子“串”在柱子上，每个盘子只能放在比它大的盘子上面。起初，所有盘子在A柱上，问题是将盘子一个一个地从A柱子移动到C柱子。移动过程中，可以使用B柱，但盘子也只能放在比它大的盘子上面。
因此我们得出汉诺塔问题的以下几个限制条件：
.在小圆盘上不能放大圆盘。
.在三根柱子之间一回只能移动一个圆盘。
.只能移动在最顶端的圆盘。
首先，我们从简单的例子开始分析，然后再总结出一般规律。
当n=的时候，即此时只有一个盘子，那么直接将其移动至C即可。移动过程就是A-C
当n=的时候，这时候有两个盘子，那么在一开始移动的时候，我们需要借助B柱作为过渡的柱子，即将A柱最上面的那个小圆盘移至B柱，然后将A柱底下的圆盘移至C柱，最后将B柱的圆盘移至C柱即可。那么完整移动过程就是A-B,A-C,B-C
当n=的时候，那么此时从上到下依次摆放着从小到大的三个圆盘，根据题目的限制条件：在小圆盘上不能放大圆盘，而且把圆盘从A柱移至C柱后，C柱圆盘的摆放情况和刚开始A柱的是一模一样的。所以呢，我们每次移至C柱的圆盘（移至C柱后不再移到其他柱子上去），必须是从大到小的，即一开始的时候，我们应该想办法把最大的圆盘移至C柱，然后再想办法将第二大的圆盘移至C柱......然后重复这样的过程，直到所有的圆盘都按照原来A柱摆放的样子移动到了C柱。
那么根据这样的思路，问题就来了：
如何才能够将最大的盘子移至C柱呢？
那么我们从问题入手，要将最大的盘子移至C柱，那么必然要先搬掉A柱上面的n-个盘子，而C柱一开始的时候是作为目标柱的，所以我们可以用B柱作为"暂存"这n-个盘子的过渡柱，当把这n-的盘子移至B柱后，我们就可以把A柱最底下的盘子移至C柱了。
而接下来的问题是什么呢？
我们来看看现在各个柱子上盘子的情况，A柱上无盘子，而B柱从上到下依次摆放着从小到大的n-个盘子，C柱上摆放着最大的那个盘子。
所以接下来的问题就显而易见了，那就是要把B柱这剩下的n-个盘子移至C柱，而B柱作为过渡柱，那么我们需要借助A柱，将A柱作为新的"过渡"柱，将这n-个盘子移至C柱。
根据上面的分析，我们可以抽象得出这样的结论：
汉诺塔函数原型：
voidHanio(intn,charstart_pos,chartran_pos,charend_pos)
那么我们把n个盘子从A柱移动至C柱的问题可以表示为：
Hanio(n,A,B,C);
那么从上面的分析得出：
该问题可以分解成以下子问题：
第一步：将n-个盘子从A柱移动至B柱（借助C柱为过渡柱）
第二步：将A柱底下最大的盘子移动至C柱
第三步：将B柱的n-个盘子移至C柱（借助A柱为过渡柱）
因此完整代码如下所示：
#includecstdio
inti;//记录步数
//i表示进行到的步数,将编号为n的盘子由from柱移动到to柱(目标柱)
voidmove(intn,charfrom,charto){
printf("第%d步:将%d号盘子%c----%c\n",i++,n,from,to);
}
//汉诺塔递归函数
//n表示要将多少个"圆盘"从起始柱子移动至目标柱子
//start_pos表示起始柱子,tran_pos表示过渡柱子,end_pos表示目标柱子
voidHanio(intn,charstart_pos,chartran_pos,charend_pos){
if(n==){//很明显,当n==的时候,我们只需要直接将圆盘从起始柱子移至目标柱子即可.
move(n,start_pos,end_pos);
}
else{
Hanio(n-,start_pos,end_pos,tran_pos);//递归处理,一开始的时候,先将n-个盘子移至过渡柱上
move(n,start_pos,end_pos);//然后再将底下的大盘子直接移至目标柱子即可
Hanio(n-,tran_pos,start_pos,end_pos);//然后重复以上步骤,递归处理放在过渡柱上的n-个盘子
//此时借助原来的起始柱作为过渡柱(因为起始柱已经空了)
}
}
intmain(){
intn;
while(scanf("%d",n)==n){
i=;//全局变量赋初始值
Hanio(n,,,);
printf("最后总的步数为%d\n",i-);
}
turn0;
}
从运行后的结果我们也可以发现：对于n个盘子，移动的总步数为^n-
体会：递归问题是个抽象的问题，因为人大脑堆栈是有限的，想象不出来运行效果，因此我们只需要枚举前几个实例，然后寻找其中规律即可。当n值增大时，只是复杂度发生了改变，实际上函数的递归调用还是一样的。
二、贪心算法：
.、算法定义所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
.、贪心算法的基本思路建立数学模型来描述问题。
.把求解的问题分成若干个子问题。
.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
.贪心算法的实现框架贪心算法适用的前提是：局部最优策略能导致产生全局最优解
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
.4贪心算法的实现框架从问题的某一初始解出发；
while（能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
.5、贪心策略的选择因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
.6、例题分析下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[背包问题]有一个背包，背包容量是M=50。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品ABCDEFG
重量
价值
分析：
目标函数：∑pi最大（价值总和最大）
约束条件是装入的物品总重量不超过背包容量：∑wi=M(M=50)
（）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（）每次挑选所占重量最小的物品装入是否能得到最优解？
（）每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
比如，求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的种贪心策略，都是无法成立（无法被证明）的，解释如下：
（）贪心策略：选取价值最大者。反例：
W=0
物品：ABC
重量：8
价值：
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（）贪心策略：选取单位重量价值最大的物品。反例：
W=0
物品：ABC
重量：
价值：
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
其实该情况是符合贪心策略的，因为该总情况不管先选哪两个都会把背包塞满，因为该题物品可以分割成任意大小，所以，就算空下一下，也可以将最后一个物品分割，放进去，它们的单位重量的价值是一样的，所以，最后背包最后重量相同，重量相同那么价值也相同。）
所以采用第三种策略，代码如下：
packagecn.itcast.cursion;
importjava.util.Arrays;
publicclassGedyPackage{
privateintMAX_WEIGHT=50;
privateint[]weights=newint[]{5,0,60,50,40,0,5};
privateint[]values=newint[]{0,40,0,50,5,40,0};
privatevoidpackageGedy(intcapacity,intweights[],int[]values){
intn=weights.length;//物品的数量
double[]r=newdouble[n];//性价比数组
int[]index=newint[n];//性价比排序物品的下标
for(inti=0;in;i++){
r=(double)values/weights;
index=i;//默认排序
}
doubletemp=0;//对性价比进行排序
for(inti=0;in-;i++){
for(intj=i+;jn;j++){
//降序，对性价比和对应下标进行排序
if(rr[j]){
temp=r;
r=r[j];
r[j]=temp;
intx=index;
index=index[j];
index[j]=x;
}
}
}
//排序好的重量和价值分别存到数组
int[]w=newint[n];
int[]v=newint[n];
//排序好的重量和价值分别存到数组
for(inti=0;in;i++){
w=weights[index];
v=values[index];
}
//用来装物品的数组
int[]x=newint[n];
//放入物品的最大价值
intmaxValue=0;
//放入物品的总重量
inttotalweights=0;
for(inti=0;in;i++){
//物品重量比包的总容量小，表示还可以装得下
if(wcapacity){
x=;//表示该物品被装了
maxValue+=v;
System.out.println(w+"kg的物品被放进包包,价值："+v);
totalweights+=w;
capacity=capacity-w;
}
}
System.out.println("总共放入的物品数量："+Arrays.toString(x));
System.out.println("总共放入的物品总重量"+totalweights);
System.out.println("放入物品的最大价值："+maxValue);
}
publicstaticvoidmain(String[]args){
GedyPackagegedyPackage=newGedyPackage();
gedyPackage.packageGedy(gedyPackage.MAX_WEIGHT,gedyPackage.weights,gedyPackage.values);
}
}
三、分治算法：
.算法定义将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
.分治策略
“分而治之”，大问题能够拆成相似的小问题，记住这些小问题需要具有相似性。而后将小问题的每个解合成为大问题的解。所以说大问题如何拆，小问题如何合并才是这个算法最主要的一个思想。实际上很多算法如贪心算法，动态规划等等都是要求把大问题拆成小问题。而分治算法的重要一点就是要适用于能够重新把小问题的解合并为大问题的解。
原问题与分解成的小问题具有相同的模式；
原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；
具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了
.4每一次递归都会涉及三个操作分解：将原问题分解成一系列子问题；
解决：递归地求解各个子问题，若子问题足够小，则直接求解；
合并：将子问题的结果合并成原问题；
.5分治法适用条件
、该问题的规模缩小到一定程度就可以很容易解决；
、该问题可以分解为若干个规模较小的相同问题，这里注意是最优子结构性质；
、利用该问题分解出的子问题的解可以合并为该问题的解；
4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共子问题；
对于很多算法而言，第一条往往是必要的，因为数据量一旦大起来，问题往往复杂度上升的特别快。这里就需要将这个大问题分解为小问题。小问题处理起来更加方便。第二、三条的才是分治思想的核心，因为很多时候我们会采用递归的方式进行解决，所以在大问题分解为小问题的时候需要保证小问题之间的相同性。单单分解为小问题之后还不能算完成，必须要能够将小问题的解合并为这个问题的最终解才能算真正用到了分治的思想。最后一条也是最关键的，各个子问题之间必须要保证独立性，即不互相影响。如果相互之间有影响，这时候我们采用的是动态规划就更加好一点。
其实算法的思想不用讲太多，能够化为几句话是最好的，下面就举几个例子来看看分治算法：
当我们遇到一个问题，完全可以在心里问自己下面四个问题：
、当前问题能不能切分？
答：能切分，因为数组按照升序来排列。所以当x大于某个元素array[mid]时，x一定在array[mid]的右边。以此再来切分。每次切一半
、分解出来的子问题相同吗？
答：相同，每个子问题的数据集都是父问题的/倍。并且每次只比较子问题的中间的数据
、子问题的解能合并为父问题的解吗？
答：不需要合并，子问题的解即为父问题的解。
4、子问题之间相互独立吗？
答：独立，子问题只是判断，不需要和父问题有很强的关联性（这里可以参考一下动态规划算法，就能理解子问题之间怎么判断是独立的）
同样在自己心里问问4个问题
、当前问题能切分吗？
答：能，最简单的就是两个数之间的比较，这个数组可以看成多个两个数来比较
、分解出来的子问题是否相同？
答：相同，都是两个数比较大小。
、子问题的解能够合成父问题的解吗？
答：每两个有序数组再按照一定顺序合起来就是最终的题解。这里就是有个合并的过程
4、子问题之间相互独立吗？
答：独立，分到最小的时候子问题之间互不影响。
下面是归并排序代码：
分治算法只是一种思想，不是一个具体的套路，只能说在碰见具体问题时我们能够从这个思路去思考，切分问题？合并问题？子问题之间影响关联大不大？这些都是具体问题具体考虑。还有很多很多题目是用了分治算法。也可以多刷刷题
设有n=^k个运动员，要进行网球循环赛。现在要设计一个满足以下要求的比赛日程表
（）每个选手必须与其他n-个选手各赛一场
（）每个选手一天只能赛一次
（）循环赛一共进行n-天
将比赛日程表设计成n行n列，表中除了第一列，其他n-列才是我们要的，数组下标行列都从0开始，第i行j列代表第（i+）位选手在第j天的对手：
以8个选手为例子，下面是填表的步骤：
①我们先初始化第一行各个数为~8（~8为：第天—第7天）；
②因为是递归，那么要填8x8的左下角和右下角，分别需要知道它的右上角和左上角
③而8x8的盒子它的左上角是一个4x4的盒子，要填4x4的左下角和右下角，也分别需要知道它的右上角和左上角
④现在递归到4x4的盒子的左上角，是一个x的盒子，它不需要递归了，直接沿对角线填左下角和右下角的数字，也就是上面的图②
⑤可以看到，经过上面的②③步，我们左上角4x4的盒子，它的·右上角和左上角已经知道了，那就可以沿对角线填它的左下角和右下角了，所以出现了图④
⑥其他的依次类推
通俗易懂地讲，就是如果你想填一个大的，你得先得出它左上角和右上角两个盒子，再沿对角线分别抄到右下角和左下角。而为了得出它左上角和右上角，就需要递归了。
packagecn.itcast.cursion;publicclassSportsSchedule{publicvoidscheduleTable(int[][]table,intn){if(n==){table[0][0]=;}else{/*填充左上区域矩阵n值的变化：84m值的变化：4*/intm=n/;scheduleTable(table,m);//填充右上区域矩阵for(inti=0;im;i++){for(intj=m;jn;j++){table[j]=table[j-m]+m;}}//填充左下区域矩阵for(inti=m;in;i++){for(intj=0;jm;j++){table[j]=table[i-m][j]+m;}}//填充右下区域矩阵for(inti=m;in;i++){for(intj=m;jn;j++){table[j]=table[i-m][j-m];}}}}publicstaticvoidmain(String[]args){int[][]table=newint[8][8];intn=8;SportsScheduleschedule=newSportsSchedule();schedule.scheduleTable(table,n);intc=0;//打印二维数组for(inti=0;in;i++){for(intj=0;jn;j++){System.out.print(table[j]+"");c++;//每打印一个数，c++if(c%n==0){//说明打印一行了System.out.println();//换行}}}}}
.9L型骨牌棋盘覆盖问题描述在一个^k×^k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格（特殊点），且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何个L型骨牌不得重叠覆盖。
解题思路分析：
当k0时，将^k×^k棋盘分割为4个^k-×^k-子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余个子棋盘中无特殊方格。为了将这个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘×。
实现：
每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角方格的行列坐标，然后再与特殊方格坐标进行比较，就可以知道特殊方格是否在该块中。如果特殊方块在里面，这直接递归下去求即可，如果不在，这根据分割的四个方块的不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继续递归。在递归函数里，还要有一个变量subSize来记录边的方格数，每次对方块进行划分时，边的方格数都会减半，这个变量是为了方便判断特殊方格的位置。
覆盖步骤如图：代码实现:packagecn.itcast.cursion;
publicclassChessBoradProblem{
privateint[][]board;//棋盘
privateintspecialRow;//特殊点行下标
privateintspecialCol;//特殊点列下标
privateintsize;//矩阵大小
privateinttype=0;//骨牌类型，,,,4因为是用数字表示的，所以用int
publicChessBoradProblem(intspecialRow,intspecialCol,intsize){
this.specialRow=specialRow;
this.specialCol=specialCol;
this.size=size;
board=newint[size][size];
}
/**
*
paramspecialRow特殊点的行下标*
paramspecialCol特殊点的列下标*
paramleftRow分割成4个后每个矩阵的左边的起点行下标*
paramleftCol分割成4个后每个矩阵的左边起点列下标*
paramsize矩阵的宽或者高*/
//相对于四个方格中右上的方格，左边起点的leftRow不一定是0了
privatevoidChessBoard(intspecialRow,intspecialCol,intleftRow,intleftCol,intsize){
if(size==){
turn;
}
intsubSize=size/;
type=type%4+;//不断+，超过4就取模
intn=type;
//假设特殊点在左上角，然后行和列都小于一半
if(specialRowleftRow+subSizespecialColleftCol+subSize){
ChessBoard(specialRow,specialCol,leftRow,leftCol,subSize);
}else{
//不在左上角，左上角矩阵的右下角就是特殊点
board[leftRow+subSize-][leftCol+subSize-]=n;
ChessBoard(leftRow+subSize-,leftRow+subSize-,leftRow,leftCol,subSize);
}
//特殊点在右上方，行小于一半，列大于一半
if(specialRowleftRow+subSizespecialCol=leftCol+subSize){
ChessBoard(specialRow,specialCol,leftRow,leftCol+subSize,subSize);
}else{
board[leftRow+subSize-][leftCol+subSize]=n;
ChessBoard(leftRow+subSize-,leftCol+subSize,leftRow,leftCol+subSize,subSize);
}
//特殊点在左下方
if(specialRow=leftRow+subSizespecialColleftCol+subSize){
ChessBoard(specialRow,specialCol,leftRow+subSize,leftCol,subSize);
}else{
board[leftRow+subSize][leftCol+subSize-]=n;
ChessBoard(leftRow+subSize,leftCol+subSize-,leftRow+subSize,leftCol,subSize);
}
//特殊点在右下方
if(specialRow=leftRow+subSizespecialCol=leftCol+subSize){
ChessBoard(specialRow,specialCol,leftRow+subSize,leftCol+subSize,subSize);
}else{
board[leftRow+subSize][leftCol+subSize]=n;
ChessBoard(leftRow+subSize,leftCol+subSize,leftRow+subSize,leftCol+subSize,subSize);
}
}
publicvoidprintBoard(intspecialRow,intspecialCol,intsize){
ChessBoard(specialRow,specialCol,0,0,size);
printResult();
}
privatevoidprintResult(){
for(inti=0;isize;i++){
for(intj=0;jsize;j++){
System.out.print(board[j]+"");//注意：print
}
System.out.println();
}
}
publicstaticvoidmain(String[]args){
intN=4;//矩阵大小
//选取特殊点
intspecialRow=0;
intspecialCol=;
ChessBoradProblemboradProblem=newChessBoradProblem(specialRow,specialCol,N);
boradProblem.printBoard(specialRow,specialCol,N);
}
}
四、动态规划：
一、基本概念
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
二、基本思想与策略
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
三、适用的情况
能采用动态规划求解的问题的一般要具有个性质：
()最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
()无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
四、求解的基本步骤
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
图动态规划决策过程示意图
()划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
()确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
()确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
实际应用中可以按以下几个简化的步骤进行设计：
（）分析最优解的性质，并刻画其结构特征。
（）递归的定义最优解。
（）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
（4）根据计算最优值时得到的信息，构造问题的最优解
五、算法实现的说明
动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。
使用动态规划求解问题，最重要的就是确定动态规划三要素：
（）问题的阶段（）每个阶段的状态
（）从前一个阶段转化到后一个阶段之间的递推关系。
递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。
确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从行列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
f(n,m)=max{f(n-,m),f(n-,m-w[n])+P(n,m)}
六、动态规划算法基本框架
代码
for(j=;j=m;j=j+)//第一个阶段
xn[j]=初始值;
4for(i=n-;i=;i=i-)//其他n-个阶段
5for(j=;j=f(i);j=j+)//f(i)与i有关的表达式
6xi[j]=j=max（或min）{g(xi-[j:j]),......,g(xi-[jk:jk+])};
8
9t=g(x[j:j]);//由子问题的最优解求解整个问题的最优解的方案
0
print(x[j]);
for(i=;i=n-;i=i+）
5{
7t=t-xi-[ji];
8
9for(j=;j=f(i);j=j+)
if(t=xi[ji])
bak;
5}
常见动态规划问题、找零钱问题有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。
测试样例：penny=[,,4]
penny_size=
aim=返回：即：方案为{，，}和{，}两种
分析：
设dp[n][m]为使用前n中货币凑成的m的种数，那么就会有两种情况：
使用第n种货币：dp[n-][m]+dp[n-][m-peney[n]]
不用第n种货币：dp[n-][m]，为什么不使用第n种货币呢，因为penney[n]m。
这样就可以求出当m=penney[n]时dp[n][m]=dp[n-][m]+dp[n][m-peney[n]]，
否则，dp[n][m]=dp[n-][m]。
penny==null
aim0){turn0;}int[][]pd=newint[n][aim+];for(inti=0;in;i++){pd[0]=;}for(inti=;penny[0]*i=aim;i++){pd[0][penny[0]*i]=;}for(inti=;in;i++){for(intj=0;j=aim;j++){if(j=penny){pd[j]=pd[i-][j]+pd[j-penny];}else{pd[j]=pd[i-][j];}}}turnpd[n-][aim];}
、走方格问题有一个矩阵map，它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。给定一个矩阵map及它的行数n和列数m，请返回最小路径和。保证行列数均小于等于00.测试样例：[[,,],[,,]],,返回：4
解析：设dp[n][m]为走到n*m位置的路径长度，那么显而易见dp[n][m]=min(dp[n-][m],dp[n][m-]);
importjava.util.*;publicclassMinimumPath{publicintgetMin(int[][]map,intn,intm){//writecodeheint[][]dp=newint[n][m];for(inti=0;in;i++){for(intj=0;j=i;j++){dp[0]+=map[j][0];}}for(inti=0;im;i++){for(intj=0;j=i;j++){dp[0]+=map[0][j];}}for(inti=;in;i++){for(intj=;jm;j++){dp[j]=min(dp[j-]+map[j],dp[i-][j]+map[j]);}}turndp[n-][m-];}publicintmin(inta,intb){if(ab){turnb;}else{turna;}}五、回溯法、概念回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
、基本思想在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
、用回溯法解题的一般步骤：（）针对所给问题，确定问题的解空间：
首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
（）确定结点的扩展搜索规则
（）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
4、算法框架（）问题框架
设问题的解是一个n维向量(a,a,………,an),约束条件是ai(i=,,,…..,n)之间满足某种条件，记为f(ai)。
（）非递归回溯框架
:inta[n],i;
:初始化数组a[];
:i=;
4:while(i0(有路可走)and(未达到目标))//还未回溯到头
5:{
6:if(in)//搜索到叶结点
7:{
8:搜索到一个解，输出；
9:}
0:else//处理第i个元素
:{
:a第一个可能的值；
:while(a在不满足约束条件且在搜索空间内)
4:{
5:a下一个可能的值；
6:}
7:if(a在搜索空间内)
8:{
9:标识占用的资源；
0:i=i+;//扩展下一个结点
:}
:else
:{
4:清理所占的状态空间；//回溯
5:i=i–;
6:}
7:}
（）递归的算法框架
回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：
:inta[n];
:try(inti)
:{
4:if(in)
5:输出结果;
6:else
7:{
8:for(j=下界;j=上界;j=j+)//枚举i所有可能的路径
9:{
0:if(fun(j))//满足限界函数和约束条件
:{
:a=j;
:...//其他操作
4:try(i+);
5:回溯前的清理工作（如a置空值等）;
6:}
7:}
8:}
9:}
知乎上关于回溯算法的分享：