【原】算法创作 | “花式”爬楼梯

问题描述

假设你正在爬楼梯。需要 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 n a,b,t=1,2,0#爬1楼1种，2楼2种 for i in range(3,n+1):#从3楼开始算     t=a+b     a=b#推导下一层     b=t return t print(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）