斐波那契数列楼梯问题代码

斐波那契数列楼梯问题是一个经典的动态规划问题，可以用递归或迭代的方式来解决。下面是一个使用递归方式解决的示例代码：

def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

def countWays(n):
    return fibonacci(n + 1)

n = int(input("请输入楼梯的阶数："))
ways = countWays(n)
print("上", n, "阶楼梯的方法数为：", ways)

上述代码中，`fibonacci`函数用于计算斐波那契数列的第n项，`countWays`函数用于计算上n阶楼梯的方法数。用户需要输入楼梯的阶数，然后程序会输出对应的方法数。

相关问题

用斐波那契数列解决爬楼梯问题

好的，对于爬楼梯问题，我们可以使用斐波那契数列来解决。假设我们有 n 阶楼梯，每次可以爬 1 阶或 2 阶，那么到达第 n 阶楼梯的方法数就是到达第 n-1 阶楼梯的方法数加上到达第 n-2 阶楼梯的方法数。因此，我们可以使用递归方法来求解，代码如下：

def climbStairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return climbStairs(n-1) + climbStairs(n-2)

但是，递归方法的时间复杂度为 O(2^n)，效率非常低，当 n 很大时，计算时间会非常长。因此，我们可以使用斐波那契数列的方法来优化求解过程。具体来说，我们可以使用两个变量 a 和 b 来记录到达当前楼梯所需要的方法数，初始值分别为 1 和 2。然后，我们可以使用循环来迭代计算，每次将 a 和 b 更新为 b 和 a+b，直到计算到第 n 阶楼梯为止。最后，返回 b 即可，代码如下：

def climbStairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        a, b = 1, 2
        for i in range(3, n+1):
            c = a + b
            a = b
            b = c
        return b

使用这种方法，时间复杂度为 O(n)，效率大大提高。

上面哪个问题代码比较简单一点？

这个问题有些难以回答，因为每个问题的难度和代码实现的复杂度都不同，而且对于不同的人来说，熟悉的问题和使用的编程语言也不同，所以选择哪个问题来实现比较简单，可能会有所不同。

不过，如果你是刚开始学习动态规划算法，建议从一些比较简单的问题入手，例如斐波那契数列问题、爬楼梯问题、零钱兑换问题等等。这些问题的状态转移方程比较简单，容易理解，而且代码实现也比较容易。

一些比较复杂的问题，例如矩阵链乘积问题、最长公共子序列问题等等，虽然难度较大，但也是非常有价值的练习题目，可以帮助你更深入地理解动态规划算法的思想和应用。