每日算法之跳台阶

JZ69 跳台阶

描述

1. 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
3. 数据范围：1 \leq n \leq 401≤n≤40
4. 要求：时间复杂度：O(n)O(n) ，空间复杂度： O(1)O(1)

复制代码

方法1 递归

思路

1. 题目分析，假设f[i]表示在第i个台阶上可能的方法数。
2. 逆向思维。如果我从第n个台阶进行下台阶，下一步有2中可能，一种走到第n-1个台阶，一种是走到第n-2个台阶。
3. 所以f[n] = f[n-1] + f[n-2]，那么初始条件了，f[0] = f[1] = 1。
4. 所以就变成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1

复制代码

代码

1. if(target == 0 || target == 1) return 1;
2.         return jumpFloor(target - 1) + jumpFloor(target - 2);

复制代码

方法2 递归改进

思路

1. f(2)计算了两次，f(1)计算了3次，f(0)计算了2次。可以采用一个数组存储已经被计算过的值
2. 此方法编译不通过，空间复杂度过高

复制代码

代码

[code]int[] f = new int[50];        if (target