LeetCode——jump-game

Q：给出一个非负整数数组，你最初在数组第一个元素的位置
数组中的元素代表你在这个位置可以跳跃的最大长度
判断你是否能到达数组最后一个元素的位置
例如
A =[2,3,1,1,4], 返回 true.
A =[3,2,1,0,4], 返回 false.

A：

public static boolean canJump(int[] A) {
        if (A.length <= 1)
            return true;
        int index = 0;
        boolean[] flag = new boolean[A.length];
        Arrays.fill(flag, false);
        flag[0] = true;
        int n;
        while (flag[index]) {
            n = index + A[index];
            if (n >= A.length - 1)
                return true;
            for (int i = index; i <= n; i++) {
                flag[i] = true;
            }
            index++;
        }
        return false;
    }

Q：给出一个非负整数数组，你最初在数组第一个元素的位置
数组中的元素代表你在这个位置可以跳跃的最大长度
你的目标是用最少的跳跃次数来到达数组的最后一个元素的位置
例如
给出数组 A =[2,3,1,1,4]
最少需要两次才能跳跃到数组最后一个元素的位置。（从数组下标为0的位置跳长度1到达下标1的位置，然后跳长度3到数组最后一个元素的位置）

A：

    public int jump(int[] A) {
        if (A.length <= 1)
            return 0;
        int[] num = new int[A.length];
        num[0] = 0;
        for (int i = 1; i < A.length; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (j + A[j] >= i)
                    min = Math.min(min, num[j] + 1);
                num[i] = min;
            }
        }
        return num[A.length - 1];
    }

LeetCode——jump-game

原文：https://www.cnblogs.com/xym4869/p/12658384.html