剑指offer题解之七——跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1. 假设当有n个台阶时假设有f(n)种走法。
2. 青蛙最后一步要么跨1个台阶要么跨2个台阶。
3. 当最后一步跨1个台阶时即之前有n-1个台阶，根据1的假设即n-1个台阶有f(n-1)种走法。
4. 当最后一步跨2个台阶时即之前有n-2个台阶，根据1的假设即n-2个台阶有f(n-2 )种走法。
5. 显然n个台阶的走法等于前两种情况的走法之和即f(n)=f(n-1)+f(n-2)。
6. 找出递推公式后要找公式出口，即当n为1、2时的情况，显然n=1时f(1)等于1，f(2)等于2
7. f(n) =1, (n=1)
   f(n) =2, (n=2)
   f(n) =f(n-1)+f(n-2) ,(n>2,n为整数)
   转变成斐波那契数列的解题方法。

总之就是用迭代不用递归就好

public class Solution {
    public int JumpFloor(int target) {
        int result=0;
        int f1=1;
        int f2=2;
        if(target<=2){
            return target;
        }else{
            for(int i=3;i<=target;i++){
                result=f1+f2;
                f1=f2;
                f2=result;
            }
        return result;
        }
    }
}