青蛙跳台阶问题和斐波那契数列

青蛙跳台阶问题和斐波那契数列是经典的编程问题。我们来分别介绍一下。

1. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？

解答：

我们可以用动态规划的思想来解决这个问题。我们用f(n)来表示跳上n级台阶的跳法数目。对于第一次跳，我们有两种选择：跳一级或者跳两级。如果第一次跳一级，那么剩下的n-1级台阶就有f(n-1)种跳法；如果第一次跳两级，那么剩下的n-2级台阶就有f(n-2)种跳法。因此，总的跳法数目就是f(n) = f(n-1) + f(n-2)，这就是斐波那契数列的定义。

那么，我们可以写出如下的Python代码来实现青蛙跳台阶的问题：

def jumpFloor(number):
    if number == 1:
        return 1
    if number == 2:
        return 2
    a, b = 1, 2
    for i in range(3, number+1):
        a, b = b, a+b
    return b

2. 斐波那契数列

斐波那契数列是指这样一个数列：0、1、1、2、3、5、8、13、21、34、……，在数学上，斐波那契数列以如下被以递归的方法定义：

$$
F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} (n \geq 2)
$$

解答：

斐波那契数列具有很好的递归性质，因此我们可以用递归的方式来求解。另一种方法是使用动态规划的思想，用f(n)来表示第n个斐波那契数，那么有f(n) = f(n-1) + f(n-2)。

我们可以写出如下的Python代码来实现斐波那契数列：

def Fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    a, b = 0, 1
    for i in range(2, n+1):
        a, b = b, a+b
    return b