第一天：《LeetCode一天一例》-----爬楼梯问题（python实现）

迷南。 2022-03-10 10:52 182阅读 0赞

# 爬楼梯问题 #

> **       题目：**小明同学爬n阶楼梯，他一次可以上一阶，也可上两阶。问小明上楼的方式有多少种？

>        解： 假设楼梯有一个台阶，则只有一种方法。 假设楼梯有两个台阶，则有两种（一次走一阶，走两次。或者一次走两阶，走一次。）。 假设楼梯有三阶呢？     你先想一下：从哪里都可以直接走到三阶？ 显然是在第一个台阶处，一下子走两阶直到三阶。或者是在第二阶，一下子走一阶，就到三阶了。。  。。 以此类推： n阶的时候有多少种方法？  那显然就是F(n-1) 加上F(n-2)。  注： F(n)表示走到n阶有多少种方法。

由此，我们用动态规划的思想， 可以写出下面的式子：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70][]

***代码实现（分别采用了递归和迭代）***

def dp_solver(n):
        # 迭代解法
    
        temp = [0] * n    # 建立一个长度为n的列表
    
        if n == 1:
            temp[0] = 1
            return temp
        elif n == 2:
            temp[0] = 1
            temp[1] = 2
            return temp
        else:
            temp[0] = 1
            temp[1] = 2
            for i in range(2, n):
                temp[i] = temp[i-1] + temp[i-2]   # 这里主要考虑到列表是从编号为0出开始存值
            return temp
    
    def recursion(n):
        # 递归解法
        if n == 1:
            return 1
        if n == 2:
            return 2
        return recursion(n-1) + recursion(n-2)
    
    if __name__ == '__main__':
    
        # 假设当前台阶我们设置为50层，问有多少种方法
        n = 10
    
        solve = dp_solver(n)
        print("爬各个层的方法:", solve)  # 打印爬各个层的方法
        print("当台阶数为:{}, 总共有{}种爬法!!!".format(n, solve[n-1]))
    
        solve2 = recursion(n)
        print("当台阶数为:{}, 总共有{}种爬法!!!".format(n, solve2))

结果输出：

![20190310220443851.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXdyb2FkODg_size_16_color_FFFFFF_t_70]: /images/20220310/402d92ef415d4bdabcdf79466fdd2bd0.png
[20190310220443851.png]: /images/20220310/db4ae8fdc6db4d42985cfb23d029fda4.png