在学习「数据结构和算法」的过程中，因为人习惯了平铺直叙的思维方式，所以「递归」与「动态规划」这种带循环概念（绕来绕去）的往往是相对比较难以理解的两个抽象知识点。
程序员小吴打算使用动画的形式来帮助理解「递归」，然后通过「递归」的概念延伸至理解「动态规划」算法思想。
什么是递归
先下定义：递归算法是一种直接或者间接调用自身函数或者方法的算法。
通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。它有如下特点：
一个问题的解可以分解为几个子问题的解
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
存在递归终止条件，即必须有一个明确的递归结束条件，称之为递归出口
递归动画
通过动画一个一个特点来进行分析。
1.一个问题的解可以分解为几个子问题的解
子问题就是相对与其前面的问题数据规模更小的问题。
在动图中①号问题（一块大区域）划分为②号问题，②号问题由两个子问题（两块中区域）组成。
2.这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
「①号划分为②号」与「②号划分为③号」的逻辑是一致的，求解思路是一样的。
3.存在递归终止条件，即存在递归出口
把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。
①号划分为②号，②号划分为③号，③号划分为④号，划分到④号的时候每个区域只有一个不能划分的问题，这就表明存在递归终止条件。
从递归的经典示例开始一、数组求和
数组求和
11Sum(arr[0...n-1])=arr[0]+Sum(arr[1...n-1])
后面的Sum函数要解决的就是比前一个Sum更小的同一问题。
11Sum(arr[1...n-1])=arr[1]+Sum(arr[2...n-1])
以此类推，直到对一个空数组求和，空数组和为0，此时变成了最基本的问题。
11Sum(arr[n-1...n-1])=arr[n-1]+Sum([])
二、汉诺塔问题
汉诺塔（HanoiTower）问题也是一个经典的递归问题，该问题描述如下：
汉诺塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。
两个盘子
①如果只有1个盘子，则不需要利用B塔，直接将盘子从A移动到C。
②如果有2个盘子，可以先将盘子2上的盘子1移动到B；将盘子2移动到C；将盘子1移动到C。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。
③如果有3个盘子，那么根据2个盘子的结论，可以借助C将盘子3上的两个盘子从A移动到B；将盘子3从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。
④以此类推，上述的思路可以一直扩展到n个盘子的情况，将将较小的n-1个盘子看做一个整体，也就是我们要求的子问题，以借助B塔为例，可以借助空塔B将盘子A上面的n-1个盘子从A移动到B；将A最大的盘子移动到C，A变成空塔；借助空塔A，将B塔上的n-2个盘子移动到A，将C最大的盘子移动到C，B变成空塔……
三、爬台阶问题
问题描述：
一个人爬楼梯，每次只能爬1个或2个台阶，假设有n个台阶，那么这个人有多少种不同的爬楼梯方法？
先从简单的开始，以4个台阶为例，可以通过每次爬1个台阶爬完楼梯：
可以通过先爬2个台阶，剩下的每次爬1个台阶爬完楼梯
先爬2个台阶
在这里，可以思考一下：可以根据第一步的走法把所有走法分为两类：
①第一类是第一步走了1个台阶②第二类是第一步走了2个台阶
所以n个台阶的走法就等于先走1阶后，n-1个台阶的走法，然后加上先走2阶后，n-2个台阶的走法。
用公式表示就是：
f(n)=f(n-1)+f(n-2)
有了递推公式，递归代码基本上就完成了一半。那么接下来考虑递归终止条件。
当有一个台阶时，我们不需要再继续递归，就只有一种走法。
所以f(1)=1。
通过用n=2，n=3这样比较小的数试验一下后发现这个递归终止条件还不足够。
n=2时，f(2)=f(1)+f(0)。如果递归终止条件只有一个f(1)=1，那f(2)就无法求解，递归无法结束。所以除了f(1)=1这一个递归终止条件外，还要有f(0)=1，表示走0个台阶有一种走法，从思维上以及动图上来看，这显得的有点不符合逻辑。所以为了便于理解，把f(2)=2作为一种终止条件，表示走2个台阶，有两种走法，一步走完或者分两步来走。
总结如下：
①假设只有一个台阶，那么只有一种走法，那就是爬1个台阶②假设有两个个台阶，那么有两种走法，一步走完或者分两步来走
递归终止条件
通过递归条件：
11f(1)=1;22f(2)=2;33f(n)=f(n-1)+f(n-2)
很容易推导出递归代码：
11intf(intn){22if(n==1)return1;33if(n==2)return2;44returnf(n-1)+f(n-2);55}
通过上述三个示例，总结一下如何写递归代码：
找到如何将大问题分解为小问题的规律
通过规律写出递推公式
通过递归公式的临界点推敲出终止条件、
将递推公式和终止条件翻译成代码
什么是动态规划
介绍动态规划之前先介绍一下分治策略（DivideandConquer）。
分治策略
将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），「递归」的求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解。
因为在求解大问题时，需要递归的求小问题，因此一般用「递归」的方法实现，即自顶向下。
动态规划（DynamicProgramming）
动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。
区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。
将「动态规划」的概念关键点抽离出来描述就是这样的：
1.动态规划法试图只解决每个子问题一次2.一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
从递归到动态规划
相同颜色代表着爬台阶问题在递归计算过程中重复计算的部分。
通过图片可以发现一个现象，我们是自顶向下的进行递归运算，比如：f(n)是f(n-1)与f(n-2)相加，f(n-1)是f(n-2)与f(n-3)相加。
思考一下：如果反过来，采取自底向上，用迭代的方式进行推导会怎么样了？
下面通过表格来解释f(n)自底向上的求解过程。
台阶数123456789走法数12
表格的第一行代表了楼梯台阶的数目，第二行代表了若干台阶对应的走法数。其中f(1)=1和f(2)=2是前面明确的结果。
第一次迭代，如果台阶数为3，那么走法数为3，通过f(3)=f(2)+f(1)得来。
第二次迭代，如果台阶数为4，那么走法数为5，通过f(4)=f(3)+f(2)得来。
由此可见，每一次迭代过程中，只需要保留之前的两个状态，就可以推到出新的状态。
showmethecode
11intf(intn){22if(n==1)return1;33if(n==2)return2;44//a保存倒数第二个子状态数据，b保存倒数第一个子状态数据，temp保存当前状态的数据55inta=1,b=2;66inttemp=a+b;77for(inti=3;i<=n;i++){88temp=a+b;99a=b;1010b=temp;1111}1212returntemp;1313}
程序从i=3开始迭代，一直到i=n结束。每一次迭代，都会计算出多一级台阶的走法数量。迭代过程中只需保留两个临时变量a和b，分别代表了上一次和上上次迭代的结果。为了便于理解，引入了temp变量。temp代表了当前迭代的结果值。
详解动态规划
「动态规划」中包含三个重要的概念：
【最优子结构】【边界】【状态转移公式】
在「爬台阶问题」中
f(10)=f(9)+f(8)是【最优子结构】f(1)与f(2)是【边界】f(n)=f(n-1)+f(n-2)【状态转移公式】
「爬台阶问题」只是动态规划中相对简单的问题，因为它只有一个变化维度，如果涉及多个维度的话，那么问题就变得复杂多了。
难点就在于找出「动态规划」中的这三个概念。
比如「国王和金矿问题」。
国王和金矿问题
有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
5座金矿
找出「动态规划」中的这三个概念
国王和金矿问题中的【最优子结构】
国王和金矿问题中的【最优子结构】有两个：
①4金矿10工人的最优选择②4金矿（10-5）工人的最优选择
4金矿的最优选择与5金矿的最优选择之间的关系是
MAX[（4金矿10工人的挖金数量），（4金矿5工人的挖金数量+第5座金矿的挖金数量）]
国王和金矿问题中的【边界】
国王和金矿问题中的【边界】有两个：
①当只有1座金矿时，只能挖这座唯一的金矿，得到的黄金数量为该金矿的数量②当给定的工人数量不够挖1座金矿时，获取的黄金数量为0
国王和金矿问题中的【状态转移公式】
我们把金矿数量设为N，工人数设为W，金矿的黄金量设为数组G[]，金矿的用工量设为数组P[]，得到【状态转移公式】：
边界值：F(n,w)=0(n<=1,w F(n,w)=g[0](n==1,w>=p[0]) F(n,w)=F(n-1,w)(n>1,w F(n,w)=max(F(n-1,w),F(n-1,w-p[n-1])+g[n-1])(n>1,w>=p[n-1]) 国王和金矿问题中的【实现】 先通过几幅动画来理解「工人」与「金矿」搭配的方式 1.只挖第一座金矿 只挖第一座金矿 在只挖第一座金矿前面两个工人挖矿收益为零，当有三个工人时，才开始产生收益为200，而后即使增加再多的工人收益不变，因为只有一座金矿可挖。 在第一座与第二座金矿这种情况中，前面两个工人挖矿收益为零，因为W<3,所以F(N,W)=F(N-1,W)=0。 当有三个工人时，将其安排挖第一个金矿，开始产生收益为200。 当有四个工人时，挖矿位置变化，将其安排挖第二个金矿，开始产生收益为300。 当有五、六个工人时，由于多于四个工人的人数不足以去开挖第一座矿，因此收益还是为300。 当有七个工人时，可以同时开采第一个和第二个金矿，开始产生收益为500。 3.挖前三座金矿 这是「国王和金矿」问题中最重要的一个动画之一，可以多看几遍 挖前三座金矿 4.挖前四座金矿 挖前四座金矿 国王和金矿问题中的【规律】 仔细观察上面的几组动画可以发现： 对比「挖第一座与第二座金矿」和「挖前三座金矿」，在「挖前三座金矿」中，3金矿7工人的挖矿收益，来自于2金矿7工人和2金矿4工人的结果，Max(500,300+350)=650； 对比「挖前三座金矿」和「挖前四座金矿」，在「挖前四座金矿」中，4金矿10工人的挖矿收益，来自于3金矿10工人和3金矿5工人的结果，Max(850,400+300)=850；