这题是用C写的~
在牛客上半天找不着ACM模式,练习模式里只有核心代码模式
这样用C语言编译器就不能自定义函数啊,不鸡肋吗???
解决方法:在核心代码模式下用C++编译器(反正C++完全兼容C的不是吗~~)
但是这样并不好,很气!

题目描述

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

示例1
输入：

2

返回值：

2

示例2
输入：

7

返回值：

21

解题思路

  • 简单递归,别说青蛙跳台阶了,兔子下楼也是一样的
  • 理解递归的思想很重要,至于什么是递归这里不多赘述(自行百度)
  • 常见的递归:斐波那契数列(1,1,2,3,5,8,13…)
  • 本题也是斐波那契哦~
  • 在递归时,往往需要自己调用自己,判断好停止时机很重要
  • 理解什么时候sum++:撞墙(搜索到头了)表示你已经走出了一条路,此时sum++
  • sum表示路径数量
  • 如果还不会,建议画图,本题是一个标准的二叉树,还是满二叉树,数叶子结点的个数
  • 一般递归都是数叶子结点的个数,如果不好理解自己调用自己,可以去理解一下二叉树
  • 当然我给出的题解是用递归做的,但是你如果观察除了斐波那契,那肯定是直接斐波那契时间复杂度低啊! 用一个数组存一串斐波那契,返回第n项a[n]就很完美了,保证AC
  • 公式:求第n个斐波那契数
  • 如果你想快速得到一个存有斐波那契数列的数组,用一个for循环不就可以搞定了么?时间复杂度O(n),真香啊!

题解

我的代码(完整版)

#include<stdio.h>
#include<math.h>

int sum = 0;
void jump(int step, int number)
{
   
    if (step >= number)
    {
   
        sum++;
        return;
    }
    else
    {
   
        jump(step + 1, number);
        if (step + 2 <= number)
            jump(step + 2, number);
    }
    return;
}

int jumpFloor(int number )
{
   
    sum = 0;
    jump(0, number);
    return sum;
}

int main()
{
   
	// for test
    printf("%d", jumpFloor(7));
    return 0;
}

在牛客上提交时的代码(真的无力吐槽了)