45.跳跃游戏

：双层for。复杂度n*n   n

class Solution {public int jump(int[] nums) {// 找到所有的条约方法，返回其中的最小次数// 从后向前，依次记录到最后的次数int n = nums.length;if(n == 1) return 0;// int[] temp = new int[n];// temp[n-1] = 0;for(int i = n - 2; i >= 0; i--){if(i + nums[i] >= n-1){temp[i] = 1;continue;}if(nums[i] == 0) {// 设置成n，意味着不可达temp[i] = n;continue;}int min = Integer.MAX_VALUE;for(int j = i+1; j <= Math.min(i+nums[i], n-2); j++){min = Math.min(min, temp[j]);}temp[i] = min+1;}return temp[0];}
}

：简化。可以直接在原数组上设置最小长。空间复杂度  1

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

 ：复杂度：n 1

public int jump(int[] nums){int range = 0;int maxRange = 0;int cnt = 0;// 注意i的条件，不要遍历最后一个元素for(int i = 0; i < nums.length - 1; i++){maxRange = Math.max(maxRange, i + nums[i]);if(i == range){cnt++;range = maxRange;}}return cnt;
}