JumpGameII.java

public class JumpGameII {

    /**
     * 动态规划
     */
    public int jump(int[] nums) {
        int[] steps = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            steps[i] = i;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    steps[i] = Math.min(steps[i], steps[j] + 1);
                }
            }
        }

        return steps[nums.length - 1];
    }

    /**
     * longestJump表示jumps步最远能到的距离
     * maxJump表示以[0,i]为起点能覆盖到的最远距离
     */
    public int jump2(int[] nums) {
        int longestJump = 0, maxJump = 0, jumps = 0;

        for (int i = 0; i < nums.length; i++) {
            // 表示i-1时还覆盖得到，而i覆盖不到了，所以更新为[0,i-1]时的maxJump
            if (longestJump < i) {
                longestJump = maxJump;
                jumps++;
            }

            maxJump = Math.max(maxJump, nums[i] + i);
        }

        return jumps;
    }


}