本篇文章为你整理了每日算法之跳台阶（跳台阶算法可以跳n级）的详细内容，包含有跳台阶 算法 跳台阶算法可以跳n级 跳台阶问题升级版 跳台阶leetcode 每日算法之跳台阶，希望能帮助你了解 每日算法之跳台阶。
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
数据范围：1 \leq n \leq 401≤n≤40
要求：时间复杂度：O(n)O(n) ，空间复杂度： O(1)O(1)
方法1 递归
题目分析，假设f[i]表示在第i个台阶上可能的方法数。
逆向思维。如果我从第n个台阶进行下台阶，下一步有2中可能，一种走到第n-1个台阶，一种是走到第n-2个台阶。
所以f[n] = f[n-1] + f[n-2]，那么初始条件了，f[0] = f[1] = 1。
所以就变成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1
if(target == 0 target == 1) return 1;
return jumpFloor(target - 1) + jumpFloor(target - 2);
方法2 递归改进
f(2)计算了两次，f(1)计算了3次，f(0)计算了2次。可以采用一个数组存储已经被计算过的值
此方法编译不通过，空间复杂度过高
int[] f = new int[50];
if (target = 1) return 1;
if (f[target] != 0) return f[target];
return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));
方法3 动态规划
思路：既然与斐波那契数列相同，我们就把它放入数组中来解决。
具体做法：
step 1：创建一个长度为n+1的数组，因为只有n+1才能有下标第n项，我们用它记录前n项斐波那契数列。
step 2：根据公式，初始化第0项和第1项。
step 3：遍历数组，依照公式某一项等于前两项之和，将数组后续元素补齐，即可得到fib[n]fib[n]fib[n]
package esay.JZ69跳台阶;
public class Solution {
public static int jumpFloor(int target) {
//方法1
/*if(target == 0 target == 1) return 1;
return jumpFloor(target - 1) + jumpFloor(target - 2);*/
//方法2
/*int[] f = new int[50];
if (target = 1) return 1;
if (f[target] != 0) return f[target];
return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));*/
//方法3
if (target = 1)
return 1;
int[] temp = new int[target + 1];
//初始化
temp[0] = 1;
temp[1] = 1;
//遍历相加
for (int i = 2; i = target; i++)
temp[i] = temp[i - 1] + temp[i - 2];
return temp[target];
public static void main(String[] args) {
System.out.println(jumpFloor(37));
以上就是每日算法之跳台阶（跳台阶算法可以跳n级）的详细内容，想要了解更多 每日算法之跳台阶的内容，请持续关注盛行IT软件开发工作室。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。