leetcode45-跳跃游戏 II

跳跃游戏 II

• 前向dp

对于一个数i，从0到i-1进行遍历，如果在这个位置能跳跃到i，那么对i的dp值进行更新。
这种方式时间复杂度为O(n^2)，效率很低

class Solution {
    public int jump(int[] nums) {
        int n = nums.length, dp[] = new int[n];
        Arrays.fill(dp, n);
        for(int i = 0; i < n; i++){
            if(i == 0)  dp[i] = 0;
            else{
                for(int j = 0; j < i; j++)
                    if(nums[j]+j >= i)  dp[i] = Math.min(dp[i], dp[j]+1);
            }
        }
        return dp[n-1];
    }
}

• 后向dp

从前向后遍历，如果当前的位置能跳跃到最后一个位置，则直接返回dp[i]+1。否则，将所有能跳跃到的位置的dp值都进行更新，取最小值。

class Solution {
    public int jump(int[] nums) {
        int n = nums.length, dp[] = new int[n];
        Arrays.fill(dp, n);
        dp[0] = 0;
        for(int i = 0; i < n-1; i++){
            if(nums[i] + i >= n-1)  return dp[i]+1;
            else{
                for(int j = i+1; j <= nums[i]+i; j++)
                    dp[j] = Math.min(dp[j], dp[i]+1);
            }
        }
        return dp[n-1];
    }
}

• 贪心+dp

不需要维护一个dp数组，而是已经遍历过的元素能达到的最大值maxPos和上一次跳跃的位置end。
一旦i == end，就意味着已经到了上一次跳跃的末尾，需要进行新一轮的跳跃，于是step++; end = maxPos;,跳跃到maxPos处

class Solution {
    public int jump(int[] nums) {
        int maxPos = 0, n = nums.length, end = 0, step = 0;
        for(int i = 0; i < n-1; i++){
            maxPos = Math.max(maxPos, nums[i]+i);
            if(i == end){
                end = maxPos;
                step++;
            }
        }
        return step;
    }
}