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)