算法（8）跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

其实无论哪一种方法思想是一样的

f（n） = f（n-1）+f（n-2）

我们通过数据可以得出这个公式，这是肉眼法。当然可以通过分析也可得出来结论。
比如要跳到 f(10) 在跳到10的前一个情况 可能在f（9） 也可能在f（8）两种可能 。所以 f（10）+f（9）这个用递归的思想去做就很好实现了。用for循环的其实也很简单，从f(3) = f(2)+f(1)开始 一层一层的往上赶。一切的起点都是一步和两步。如下如所示。把握住这个核心就可以了。

递归方法

 public static int JumpFloor(int target) {
        //最后没有了
        if (target == 0) {
            return 0;
        }
        //最后剩一个
        if (target == 1) {
            return 1;
        }
        //最后剩两个
        if (target == 2) {
            return 2;
        }

        return JumpFloor(--target) + JumpFloor(--target);

    }

for循环方法

 public static int JumpFloor1(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;
        
    }