在介绍此算法之前，我线抛出几道题目，当然这几道题目均出自于剑指offer大家可以简单思考一下。
Q1:大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
Q2:一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
Q3:一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
Q4:我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
第一道题我想大学刚学C的时候上机实验就应该有这道题，一道很简单的递归题，代码如下。
public class Solution {
public int Fibonacci(int n) {
if(n>39){
return -1;
}
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
然而第二，三，四题呢?有没有具体的解题思路呢?所以，我认为，在解决这种一眼看上去很简单，但是又无从下手给出具体的代码思路的时候，通常可以用数学归纳法
首先我们来看第一题：
我们设台阶一共有n级，当n=1，2，3，4时分别有几种跳法呢？
n=1；jumpWays=1(即：1);
n=2；jumpWays=2(即：1-1,2);
n=3；jumpWays=3(即：1-1-1,1-2,2-1);
n=4；jumpWays=5(即：1-1-1-1,1-2-1,2-1-1,1-1-2,2-2);
好了，接下来就不用继续往下推了吧？而且大家很容易就能归纳出来即：
f(n) = f(n-2)+f(n-1),当n==1时，return1；当n==2时，return 2；
这不就是斐波那契数列吗？
代码如下
public class Solution {
public int JumpFloor(int target) {
if(target == 1){
return 1;
}
if(target == 2){
return 2;
}
return JumpFloor(target-1)+JumpFloor(target-2);
}
}
同样我们来看第二题：
我们设台阶一共有n级，当n=1，2，3，4时分别有几种跳法呢？
n=1；jumpWays=1(即：1);
n=2；jumpWays=2(即：1-1,2);
n=3；jumpWays=4(即：1-1-1,1-2,2-1,3);
n=4；jumpWays=8(即：1-1-1-1,1-2-1,2-1-1,1-1-2,2-2,1-3,3-1,4);
好了，接下来就不用继续往下推了吧？而且大家很容易就能归纳出来即：
f(n) = 2的n-1次方，当n==1时，return 1；（这里貌似简书markdown不支持函数格式？ex:2^{n-1}）
代码如下
public class Solution {
public int JumpFloorII(int target) {
if(target == 1){
return 1;
}
return 2*JumpFloorII(target-1);
}
}
最后一题当然留给大家自己思考归纳一下了？我认为这样才能有收获的🐴。
最后总结一下：我认为呢？通常碰到那种看上去逻辑简单的，但是没有思路去写代码的时候，不妨利用数学归纳法，推理一下当n很小的时候的几种情况，看看能不能从中找出规律。
