Python教程

Python编程题26--爬楼梯

本文主要是介绍Python编程题26--爬楼梯,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。请问有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数,其范围为:1 ≤ n ≤ 100。

例如:

给定一个正整数:2,返回结果:2

说明:共有 2 种方法爬到楼顶,第一种为 1阶 + 1阶,第二种为 2 阶。

给定一个正整数:3,返回结果:3

说明:共有 3 种方法爬到楼顶,第一种为 1阶 + 1阶 + 1阶,第二种为 1阶 + 2阶,第三种为 2阶 + 1阶。

实现思路

分析上面题目,可以发现第 n 个台阶只能从第 n-1 个台阶或第 n-2 个台阶走上去,那么就可以得到以下结论:

第 n 个台阶的走法 = 第 n-1 个台阶的走法 + 第 n-2 个台阶的走法

看到这里,是不是感觉很熟悉,没错,这不就是 斐波那契数列 嘛,不同的地方在于我们这里的第1项值是1,第二项值是2。那么接下来应该就很简单了,我们要做的就是求出 斐波那契数列 的第 n 项。

之前有写过关于 斐波那契数列 的题目,可以前往了解:Python编程题9--斐波那契数列

代码实现--非递归

def climbStairs(n):
    a, b = 1, 1
    while n > 1:
        a, b = b, a + b
        n -= 1
    return b

代码实现--递归

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

如果在算法题中,当 n 的值比较小时,上面递归解法是没什么没问题的,但如果 n 的值较大,比如上面的 n = 100 ,这个时候必然会提示超出时间限制。

return climbStairs(n - 1) + climbStairs(n - 2)

在上面代码中,每次都需要2次递归,同时会出现大量的重复计算,随着 n 的增大,导致耗时非常久,性能变得非常差,另外调用函数次数过多,也容易出现栈溢出。

因此,我们对递归代码进行优化如下:

def climbStairs_recursive(n, first, second):
    if n == 1 or n == 2:
        return n
    elif n == 3:
        return first + second
    return climbStairs_recursive(n - 1, second, first + second)

def climbStairs(n):
    return climbStairs_recursive(n, 1, 2)

优化后的代码中,我们每次只需要1次递归,并且直接通过 first、second 记录当前相加的2个数值,避免了重复计算。

这篇关于Python编程题26--爬楼梯的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!