"剑指Offer"里的经典题目,近期群里聊到这题,特来复习一波.
求该青蛙跳上一个 n 级的台阶总共有多少种跳法.
首先跳到 n 级台阶可以分解为两种情况:
因此 n 级跳法数量,等于这两种情况之和.
同理可继续推导:
可见这是斐波那契数列,数列中从第三个数开始,每个数都是前两个数之和.那么只需从 F(0) + F(1) = F(2) 开始计算,一直加到 F(n) 即可得出结果.
其他解法还包括递归法,把 F(n) 不断拆解递归,也就是上面推导的前半部分,感兴趣可以自己尝试一下.
本文参与"OSC源创计划",欢迎正在阅读的你也加入,一起分享.