跳台阶扩展问题【Java版】
跳台阶扩展问题
http://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387
1)找出公式
public class Solution { public int JumpFloorII(int target) { int way=1;for(int i=1;i<target;i++)way*=2;return way; } } //【找出数学公式】2的n-1次方:类似向n个点之间的n-1个空画横线 // 其实不难找,在找递推公式时,前几项一写就知道了 // 时间 O(N) // 空间 O(1)
2)(动态规划)硬算
public class Solution { public int jumpFloorII(int target) { int[] array =new int[100]; array[1] = 1; for(int i=2; i<=target; ++i){ int sum = 0; for(int j=1; j<=i-1; ++j)sum+=array[j]; array[i] = sum +1; //之前所有路径,再加上直接全部的1个跳法 } return array[target]; } } //时间 O(N^2) //空间 O(N)
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》