题目:https://www.nowcoder.com/ta/coding-interviews
这是在“面试题10:非波拉契数列”中的另一个题目
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
理解:
如果有1级台阶,只有1种 ;如果有2级台阶,有1–1、2两种 ;如果有3级台阶,有1–1–1、1–2、2–1三种跳法
假设n级台阶有F(n)种跳法,一定是先跳1级或者先跳2级这两类方式,再继续跳到n级台阶,跳1级后有F(n-1)种,跳2级后有F(n-2)种,故共有F(n)=F(n-1)+F(n-2)。这与斐波拉契数列一致。
但是跳台阶没有0级台阶:F(1)=1,F(2)=2,F(3)=3,F(4)=5,…,F(n)=F(n-1)+F(n-2),…
1 | class Solution1: |
1 | method = Solution1() |
8
1 | class Solution: |
1 | method = Solution() |
8
1 |