《剑指Offer》08跳台阶
题目:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
思路:
第一种方法很简单,递归,没想到牛客OJ竟然过了时间复杂度为O(2^n)的解法。
public class Solution { public int JumpFloor(int target) { if (target==1) { return 1; } if (target==2) { return 2; } return JumpFloor(target-1)+JumpFloor(target-2); } }
第二种解法,时间复杂度为O(n)的解法:
public class Solution { public int JumpFloor(int target) { if (target==1) { return 1; } if (target==2) { return 2; } int num1 = 1; int num2 = 2; int num3 = 0; for (int i=3; i<=target; i++) { num3 = num1+num2; num1 = num2; num2 = num3; } return num3; } }