题目出自《剑指offer》，整理自https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
1. 问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
2. 思路
首先我选择的是循环，每次有跳1个台阶或2个台阶的可能，然后减去跳过的台阶，但是接下来就没有思路了。
于是又考虑递归，考虑分治法，考虑第一次跳有2种方法，第二次又有两种。考虑到边界条件,递归外边的target = 1，target = 2 这两种情况就分别返回1，2即可
//特殊情况
if(target == 1){
return 1 ;
}
if(target == 2){
return 2;
}
return getNum(target);
重点来看下递归体,重要部分我暂时没放出来，终止条件很好理解，就是只剩1和2的情况，直接返回1和2
public int getNum(int target){
if(target == 1){
return 1;
}else if(target == 2){
return 2;
}else{
return ？？？？？;
}
}
对于 ？？？？？ 部分，我一开始写的是。
2 * getNum(xxx);
显然不对，xxx不知道要传什么了，是传target - 1 还是 target - 2？无解，
结合刚才所提到的分治法，我们的目的就是把大问题划分成小问题去求解，
我们第一次跳1个台阶，那么接下来就剩target - 1 的台阶，对于target - 1就是一个子问题，我们逐步缩小规模，直到最后产生最小的子问题，剩1个，或者剩2个。
那这样分析过后，就显得清楚了许多，我写了如下内容
return getNum(target - 1) + getNum(target - 2);
思考递归，千万不要刨根问底。
思考递归，千万不要刨根问底。
思考递归，千万不要刨根问底。
这是一个忠告，站在宏观的角度上理解递归，懵不懵逼是程序自己的事儿，不是程序猿的事儿，作为一个程序猿，你只需要在大局下知道你这个语句是求了个啥，你就不害怕递归了。
上面的求了个啥？
为啥这样写，还不是因为我们思考上一个代码的时候，传参不会写了？
那么既然-1也不合适，-2也不合适，分成两块好了。
第一块求如果是-1 是啥情况呢？
第二块求如果是-2 是啥情况呢？
相加，Perfect,所有的情况都包含了。
但一旦你试图去理解，-1是怎么运行的，子问题还得-2 ，balabala……
那么恭喜你已经进入了下面这个状态！
如果你说了，你上面讲的宏观 我才做不到呢，你给我讲讲怎么运行的！
好好好，那我就给你画图说一说吧。
image.png
瞧瞧，瞧瞧，这优雅的画技。
首先target = 5进入递归，调用getNum(target - 1) 与 getNum(target - 2)
产生了4和3两个子问题，4和3说，我不知道答案，我去问问我孩子。
然后产生了3，2 和2，1，同样他们3说我也不知道，我得去问我孩子，而其他的都说我知道，分别返回了自己的值。
最后3也找到了它的孩子2，1，分别返回了自己的值。
那么问题来了，值是多少？
刚才说了，2是返回2的，1是返回1的，
你数数树杈子，看看到底是几嘛！
什么还不懂？
斐波那契数列了解一下。
3.完整代码
public static int JumpFloor(int target) {
if(target == 1){
return 1 ;
}
if(target == 2){
return 2;
}
return getNum(target);
}
public static int getNum(int target){
if(target == 1){
return 1;
}else if(target == 2){
return 2;
}else{
return getNum(target - 1) + getNum(target - 2);
}
}
4. 运行
先去吃饭，吃完饭更！
仔细看上面的递归树，会发现有很多重复的调用
由此看来性能也不会很好，所以我们就要考虑循环版本了。
https://www.nowcoder.com/profile/214250/codeBookDetail?submissionId=1520111
public class Solution {
public int JumpFloor(int target) {
if(target <= 0) return 0;
if(target == 1) return 1;
if(target == 2) return 2;
int one = 1;
int two = 2;
int result = 0;
for(int i = 2; i < target; i++){
result = one+ two;
one = two;
two = result;
}
return result;
}
}
for循环内，是不断更新斐波那契数的过程。
两种算法的算法复杂度分析如下：
递归算法：
二叉树的高度是 n - 1，由我们的基础知识可以知道，一个高度为k的二叉树最多可以由 2^k - 1个叶子节点，也就是递归过程函数调用的次数，所以时间复杂度为 O(2^n)，而空间复杂度就是树的高度 S(n)
循环算法：
时间：O(n)
空间：O(1)
5. 结束
结束了，没啥说的，最近复习复试很焦躁，月底就要结束这煎熬了，这一年很充实，希望复试成功吧！
网友评论