每日刷题_牛客_跳台阶

题目描述

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

主要思路

如果你刚看完上到的斐波那契数列，再看这道题是不是有些熟悉。没有？高数中有个很牛皮的找规律方法。相信你一定知道它是啥 。【数学归纳】
但大致看一下
首先看跳第一级。只要一种方法
跳第二级有。2种
跳第三级呢。先看是怎么跳上第三级的。它可是是从3-1级跳的，也可能是从3-2级跳的。跳3-1级也就是第二级的方法已经有了，同理跳到3-2级也就是第一级的方式也就用了。（只要我们有点概率论的基础我们就知道这里要做加法操作）即跳第三级的方式=第一级的方式+跳第二级的方式

那么第i级呢 同理（i-1）的方式+（i-2）的方式

这不就是斐波那契数列的算法吗
不同点在于。斐波那契数列的第二项=第零项+第一项=1
这里的可不是。这里跳到第二级的方式是2
修改一下即可

我的代码

//方法一。重新设置n=2的值
        function jumpFloor(number) {
            // write code here
            if (number == 0) {
                return 0;
            }
            if (number == 1) {
                return 1;
            }
            if (number == 2) {
                return 2;
            }
            let arr = [];
            arr[0] = 0;
            arr[1] = 1;
            arr[2] = 2;
            for (let i = 3; i <= number; i++) {
                arr[i] = arr[i - 1] + arr[i - 2]
            }


            return arr[arr.length - 1];

        }
        //方法2：找其与斐波那契数列的关系。发现可以不用改n=2的值。斐波那契数列索引后移一位即可
function jumpFloor(number)
{
    // write code here
    if (number == 0) {
                return 0;
            }
            if (number == 1) {
                return 1;
            }
            let arr = [];
            arr[0] = 0;
            arr[1] = 1;
            for (let i = 2; i <= number+1; i++) {
                arr[i] = arr[i - 1] + arr[i - 2]
            }
            

            return arr[arr.length-1];

        }