跳台阶【Java版】
跳台阶
http://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
1)斐波拉切-O(N)动态规划
public class Solution { public int JumpFloor(int target) { int frog[]=new int[100]; frog[1]=1;frog[2]=2; for (int i=3;i<=target;i++){ frog[i]=frog[i-1]+frog[i-2]; } return frog[target]; } } //原理同:斐波那契数列 //【动态规划】时间O(N),空间O(N) //如果只要最后的结果,那么可以撤销数组,使用a/b/c三个变量存储即可。空间复杂度减为O(1)
2)空间O(1)的方法
public class Solution { public int jumpFloor(int target) { if(target<=2)return target; int lastOne = 2; //现在位置上一个,相当于fi[i-1] int lastTwo = 1; //相当于fi[i-2] int res = 0; for(int i=3; i<=target; ++i){ res = lastOne + lastTwo; lastTwo = lastOne; lastOne = res; } return res; } } //这种方法的空间复杂度为:O(1) //时间复杂度虽然也为O(N),但是比上一种动态规划的方法耗时,因为循环里面操作较多 //相当于时间换空间,花费时间在不断倒腾地方
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》