贪心/dp | 跳跃游戏
跳跃游戏 II
贪心+双指针+DP

简单来说,对于下一个点j的最小次数,其必定是由离他最远的点跳过去的次数最少。
但是反过来不太行,如果是考虑当前点,只让他跳到最远的点的话,相当于这个点对应的下一步只有一个点,但这是不对的。因为他可能对应着多个点。但对于下一个点来说,他的最优只会有一个。
状态定义 f[i] 为达到第i个位置所需要的最少步数 转移方程: f[i] = f[j]+1;
public int jump(int[] nums) { int n = nums.length; int[] f = new int[n]; for(int i=1,j=0;i<n;i++) { while(j+nums[j]<i) j++ ; // 只要j指针+当前对应的可跳步数是能够到达i的,就不用更新j指针。 f[i] = f[j] + 1; } return f[n-1] ; }
纯贪心
按照正常的想法,对于每一步,可以选择他跳最远的地方,但是要看这一步的跳跃+下一步的跳跃距离来决定哪个是该选的,能跳最远的。且,指针不能直接跳过去,对于每一个元素,都需要进行一次遍历。因为决定的只有到第二层,而实际情况到了第n层。
在具体的实现中,我们维护当前能够到达的最大下标位置,记为边界。我们从左到右遍历数组,到达边界时,更新边界并将跳跃次数增加1.
在遍历数组时,我们不访问最后一个元素,这是因为在访问最后一个元素之前,我们的边界一定大于等于最后一个位置,否则就无法跳到最后一个位置了。如果访问最后一个元素,在边界正好为最后一个位置的情况下,我们会增加一次【不必要的跳跃次数】,因此我们不必访问最后一个元素。
public int jump(int[] nums) { int length = nums.length; int end = 0; int maxPosition = 0; int steps = 0; for(int i=0;i<length-1;i++){ maxPosition = Math.max(maxPosition,i+nums[i]); if(i==end) { end = maxPosition; steps++; } } return steps ; }