08-青蛙🐸跳-动态规划

题目描述

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

分析

• 分析可知这是斐波那契数列，所以可以动态规划来做

  a.如果两种跳法，1阶或者2阶，
  b.那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
  c.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
  d.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
  e.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
  f.可以发现最终得出的是一个斐波那契数列

代码

function jumpFloor(number) {
  // write code here
    if(number==1) return 1;
    if(number==2) return 2;
    let last = 1;
    let nextLast = 2;
    let res ;
    for(let i=2;i<number;i++){
        res = last + nextLast;
        last = nextLast;
        nextLast = res;
    }
    return res;
}