题目

55. 跳跃游戏

题解


代码

public class code55 {

    public static boolean canJump(int[] nums) {
        if (nums == null) {
            return false;
        }
        int lastPosition = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
        // 逐步向前递推 
            if (i + nums[i] >= lastPosition) {
                lastPosition = i;
            }
        }
        if (lastPosition == 0) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        int nums1[] = { 2, 3, 1, 1, 4 };
        boolean flag1 = canJump(nums1);
        System.out.println(flag1);

        int nums2[] = { 3, 2, 1, 0, 4 };
        boolean flag2 = canJump(nums2);
        System.out.println(flag2);
    }
}

参考

  1. 跳跃游戏——题解一
  2. 动态规划与贪心算法解决此问题——题解二