题解 | #跳台阶扩展问题#

public class Solution {
    public int jumpFloorII(int target) {
        if (target <= 0) return 0;
        int[] dp = new int[target + 1];
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            int sum = 1;
            for (int j = 1; j <= i; j++) {
                sum += dp[j];
            }
            dp[i] = sum;
        }
        return dp[target];
    }
}

// 或者数学公式：f(n)=2^(n+1)
public int JumpFloorII(int target) {
  return (int) Math.pow(2, target - 1);
}

解题思想：动态规划，由已知求未知，dp保存前面算出的值，后面是前面每个台阶累积和。或者直接数学公式得出：f(n)=2^(n+1)