public boolean canJump1(int[] A) {// O(n^2) and O(n) space
		if (A.length <= 1)
			return true;
		boolean[] canReach = new boolean[A.length];
		for (int i = A.length - 2, dist = 1; i >= 0; --i, ++dist) {
			if (A[i] >= dist) {
				canReach[i] = true;
			} else {
				int j = 1;
				while (j <= A[i] && !canReach[i + j])
					++j;
				if (j <= A[i])
					canReach[i] = true;
			}
		}
		return canReach[0];
	}