面试题Fibonacci数列：一个台阶总共有n级，如果一次可以跳

思路：

• 如果只有1 级台阶，只有一种跳法；
  如果有2 级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1 级；另外一种就是一次跳2 级。
  如果有3级台阶，那就有4种跳的方法：一种是分3次跳，每次跳1级；另一种是一次跳1级，一次跳2级（调换过来也是一种）；另一种是一次就跳3级；

• 一般情况：把n 级台阶时的跳法看成是n 的函数，记为f(n)。
  当n>3 时，第一次跳的时候就有3种不同的选择：

  • 一种是第一次只跳1 级，此时跳法数目等于后面剩下的n-1 级台阶的跳法数目，即为f(n-1)；
  • 另外一种选择是第一次跳2 级，此时跳法数目等于后面剩下的n-2 级台阶的跳法数目，即为f(n-2);
  • 另外一种选择是第一次跳3 级，此时跳法数目等于后面剩下的n-3 级台阶的跳法数目，即为f(n-3)。

• 因此n 级台阶时的不同跳法的总数f(n) = f(n-1) + f(n-2) + f(n-3)。
  时间复杂度：O(n)

public class Test {
    public static void main(String[] args) {
        System.out.println(jump(4));
    }

    private static int jump(int step) {
        // TODO Auto-generated method stub
        if(step <= 0) {
            return 0;
        }
        if(step == 1 || step == 2) {
            return step;
        }
        if(step == 3) {
            return step + 1;    //包括自身
        }
        return (jump(step - 1) + jump(step - 2) + jump(step - 3));
    }
}

输出结果是：7