剑指 offer 笔记 08 | 跳台阶

题目描述

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

题目分析：
本题可以用递归和迭代来解答，那么就是要找规律了。因为青蛙只有 一次 1 阶或者 2 阶的跳法。

递归法：

1）当台阶为 1 时，只有一种跳法，一步到位。

2）当台阶为 2 时，有两种，一种是分两次跳，每次为 1；第二种，跳一次，一次跳两级；

3）从特殊推测到一般情况，假定第一次跳的是 1 阶，那么剩下的是 n-1 个台阶，跳法是 f(n-1);

4）假设第一次跳的是 2 阶，那么剩下的是 n-2 个台阶，跳法是 f(n-2)；

5）由 3）和 4）假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) ；

6）最终得出的是一个斐波那契数列：
| 1, (n=1)
f(n) = | 2, (n=2)
| f(n-1)+f(n-2) ,(n>2,n为整数)

额外补充：
直接找规律，f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5， 可以总结出f(n) = f(n-1) + f(n-2)的规律；

假设现在 6 个台阶，我们可以从第 5 跳一步到 6，这样的话有多少种方案跳到 5 就有多少种方案跳到 6；

另外我们也可以从 4 跳两步跳到 6，跳到 4 有多少种方案的话，就有多少种方案跳到 6，其他的不能从 3 跳到 6 什么的啦；

所以最后就是 f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。

public class Solution {
    public int JumpFloor(int target) {
        if (target <= 0) {
            return -1;
        } else if (target == 1) {
            return 1;
        } else if (target ==2) {
            return 2;
        } else {
            return  JumpFloor(target-1)+JumpFloor(target-2);
        }
    }
}

迭代法：

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 0) {
            return 0;
        }else if(target == 1) {
            return 1;
        }else  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;
    }
}

参考文献：https://www.nowcoder.com/profile/214250/codeBookDetail?submissionId=1520111