跳台阶

  1. 题目描述
  2. 分析
  3. 变态版

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

分析

  • 原理就是斐波那契数列
// 递归实现
class Solution {
public:
    int jumpFloor(int number) {
        if (number == 1) return 1;
        if (number == 2) return 2;
        return jumpFloor(number - 1) + jumpFloor(number - 2);
    }
};

变态版

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

class Solution {
public:
    // 数学归纳法证明 有 2^(n-1)中情况
    int jumpFloorII(int number) {
        if (number == 0) return 0;
        int res = 1;
        for (int i = 1; i < number;i++){
            res *= 2;
        }
        return res;
    }
};

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 1056615746@qq.com

文章标题:跳台阶

字数:202

本文作者:攀登

发布时间:2019-12-26, 23:12:31

最后更新:2024-06-15, 15:53:35

原始链接:http://jiafeimao-gjf.github.io/2019/12/26/sword-%E8%B7%B3%E5%8F%B0%E9%98%B6/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

×

喜欢就点赞,疼爱就打赏