算法刷题|跳台阶

题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。


思路:如果只有一级台阶,则只有一种跳法(1);如果有两级台阶,则有两种跳法:(1,1;2);如果有三级台阶,则有三种跳法:(1,1,1;1,2;2,1);如果有四级台阶,则有五种跳法:(1,1,1,1;1,1,2;1,2,1;2,1,1;2,2;)......依次类推可以发现如下规律:

        当n=1,f(n)=1;

         当n=2,f(n)=2;

         当n>=3,f(n)=f(n-1)+f(n-2);

可以采用两种方法,一种是用递归,另一种是迭代。


实现代码:

迭代方法:


第二个方法为递归。递归比迭代运行时间要更久一点。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • You are climbing a stair case. It takes n steps to reach ...
    stevewang阅读 1,491评论 0 3
  • 最近在刷一些数据结构的题,发现个很有趣的问题:跳台阶问题。 1. 第一题(引子):输出菲波那切数列的第N项。 斐波...
    MentallyL阅读 2,900评论 1 6
  • 本文出自 Eddy Wiki ,转载请注明出处:http://eddy.wiki/interview-code.h...
    eddy_wiki阅读 9,364评论 0 30
  • 范畴:递归 1、青蛙跳台阶 青蛙跳台阶算法,每次可以跳1级或两级,请问有n级台阶,有多少种算法,递归和非递归如何写...
    夷陵小祖阅读 461评论 0 1
  • 作者:唐太宗(唐代) 条风开献节,灰律动初阳。 百蛮奉遐赆,万国朝未央。 虽无舜禹迹,幸欣天地康。 车轨同八表,书...
    妖气迷人阅读 233评论 0 3