算法创作 | “花式”爬楼梯
问题描述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。示例 1:输入:2输出:2解释:有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶示例 2:输入:3输出:3解释:有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶解决方法这是力扣题库中较简单的一题,首先定义一个函数climbStairs()据题意知,当楼梯阶数为1只有1种,为2时只有2种,则单独设一种情况。再分析3阶及以上的,初始化爬到n楼的方法,台阶每次是可以爬一个或两个,注意for循环时从3楼开始算,t=a+b,再推导下一层,最后返回t,def climbStairs(n):if n==1 or n==2:return na,b,t=1,2,0#爬1楼1种,2楼2种for i in range(3,n+1):#从3楼开始算t=a+ba=b#推导下一层b=treturn tprint(climbStairs(2))print(climbStairs(7))这个是偏数学解法, 假设我们现在站在台阶i上面。对于我们如何到达的i,有且仅有两种可能:我们之前在台阶i-1上面,然后用一步走到了台阶i上面;我们之前在台阶i-2上面,然后用两步走到了台阶i上面。设函数f(i)为到达i的所有可能的方法数量。则有f(i) = f(i-1) + f(i-2)即到达i的方法数等于到达i-1的方法数加上到达i-2的方法数。def climbStairs(n):f=[1,2]for i in range(2,n):f.append(f[i-1]+f[i-2])return f[n-1]print(climbStairs(2))print(climbStairs(7))运行结果:
结语对爬楼梯提出了两种算法,不同的思路。游戏式的爬楼梯,会在不知不觉中到达。实习编辑:李欣容稿件来源:深度学习与文旅应用实验室(DLETA)