JZ8 — 跳台阶

题目描述

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

题目分析

这道题和上一题是相同的题目，递归或者递推都可以解决，不再赘述。
参考：http://www.guanhaobo.cn/?p=684

青蛙跳上第n级台阶，一共有两种方式：
1. 从第n-1级台阶一次跳上1级台阶到达第n级台阶
2. 从第n-2级台阶一次跳上2级台阶到达第n级台阶

因此有f[n] = f[n-1] + f[n-2]

C++

class Solution
{
public:
    int jumpFloor(int number)
    {
        if (number < 3)
            return number;
        int a3, a2 = 2, a1 = 1;
        for (int i = 3; i <= number; i++)
        {
            a3 = a2 + a1;
            a1 = a2, a2 = a3;
        }
        return a3;
    }
};

Java

public class Solution {
    public int JumpFloor(int target) {
        if (target < 3)
            return target;
        int a3 = 3, a2 = 2, a1 = 1;
        for (int i = 3; i <= target; i++) {
            a3 = a2 + a1;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }
}