跳台阶

Introduction

Question：跳台阶

Analysis

一道比较经典的题目，但是很简单。一只青蛙想要跳上第 n 级的跳法可以分成两种：

• 从第 n - 1 级跳上来
• 从第 n - 2 级跳上来

所以可以写出以下递推公式：

$$
\begin{equation}
\begin{aligned}
jumpFloor(n) && = jumpFloor(n-1) + jumpFloor(n-2) &&, n >= 2 \
jumpFloor(n) && = 1 &&, n == 0 || n == 1
\end{aligned}
\end{equation}
$$

如你所见，这其实就是求解一个斐波那契数列。

Implement

int jumpFloor(int number) {
    // return number <= 1 ? 1 : jumpFloor(number-1) + jumpFloor(number-2);
    if (number <= 1) return 1;
    int a, b; a = b = 1;
    for(int i = 2;i <= number;i++) {
        swap(a, b);
        b = a + b;
    }
    return b;
}

One More Thing