一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
数据范围:
要求:时间复杂度: ,空间复杂度:
export function jumpFloor(number: number): number { // write code here let res = 0; let a1 = 0; let a2 = 1; while (number--) { res = a1 + a2; a1 = a2; a2 = res; } return a2; // 1 1 // 2 2 // 3 2+1 // 4 3+2 // 5 5+3 // 6 8+5 // 7 13+8 斐波那契数列的应用 }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param number int整型 * @return int整型 */ export function jumpFloor(number: number): number { // write code here let target = { 1: 1, 2: 2, 3: 3, 4: 5 } function _jumpFloor(num){ if(target[num]) return target[num] else { const res = _jumpFloor(num - 1) + _jumpFloor(num - 2); target[num] = res; return res } } return _jumpFloor(number) }
export function jumpFloor(number: number): number { // write code here if(number <= 0){ return 0; } if(number === 1){ return 1; } if(number === 2){ return 2; } let first:number = 1,second:number = 2 ,third:number = 0; for(let i = 3; i <= number;i++){ third = first + second; first = second; second = third; } return third }
对于本题,前提只有 一次 1阶或者2阶的跳法。
a.如果两种跳法,1阶或者2阶,那么假定第一次跳的是一阶,那么剩下的是n-1个台阶,跳法是f(n-1);
b.假定第一次跳的是2阶,那么剩下的是n-2个台阶,跳法是f(n-2)
c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
d.然后通过实际的情况可以得出:只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
e.可以发现最终得出的是一个斐波那契数列:
| 1, (n=1)
f(n) = | 2, (n=2)