题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
规则示例
规则
1 <= n <= 45
示例 1:
输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
解题分析一:动态规划
本题是一个典型的以斐波那契数列为考点的题目
粗暴的一句话总结斐波那契数列的规律:
从第三个数开始,之后的每个数的值是前两个数相加的结果
我们以1到5阶上台阶的方式举例:
1个台阶—>1种方式
1
2个台阶—>2种方式
1 + 1
2
3个台阶—>3种方式
1 + 1 + 1
1 + 2
2 + 1
4个台阶—>5种方式
1 + 1 + 1 + 1
2 + 2
1 + 1 + 2
2 + 1 + 1
1 + 2 + 1
5个台阶—>8种方式
1 + 1 + 1 + 1 + 1
2 + 2 + 1
2 + 1 + 2
1 + 2 + 2
1 + 1 + 1 + 2
2 + 1 + 1 + 1
1 + 2 + 1 + 1
1 + 1 + 2 + 1
以此类推
我们发现从第3个台阶开始,就有了每个数的值是前两个数相加的结果这一规律
斐波那契数列典型规则
因此我们这道题的最简单的解法就是把爬n阶楼梯的方法数量分解为两部分之和:
得到爬上n-1阶楼梯的方法数量
得到爬上n-2阶楼梯的方法数量
那么就可以得到信息:
方法数量(n) = 方法数量(n - 1) + 方法数量(n - 2)
方法数量(1) = 1
**方法数量(2) = 2 **
那我们可以通过循环,从3阶楼梯开始计算当前阶的方法数量,计算完后改变上一阶和上上一阶的结果,不停的往后计算即可。
解题一:动态规划
解题分析二:数学公式
如果发现了是斐波那契数列,那么我们也可以直接使用现成的斐波那契数列公式进行计算得到结果,斐波那契公式:
斐波那契公式
只要记住这个公式,那么我们可以通过实现一个数学计算函数来得到结果。
解题二:数学公式
总结
只要解决过一次斐波那契数列的题目,那么之后遇到类似的题是就应该不会遇到太多困难,斐波那契数列是经典的笔试题目,希望大家都能够将其掌握。
END