跳台阶扩展问题【Java版】

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)