Leetcode 45. 跳跃游戏 II（DP 双指针）

Leetcode 45. 跳跃游戏 II

动态规划

使用dp [ ] 记录每个位置可达的最小步数，每到达一个点时，更新该点所能跳跃区间内的所有点的dp值
时间复杂度较高

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

优化 双指针

双指针 l r 表示目前可达的区间左右端点，遍历区间维护一个可达的最远距离maxPos
当 l r 相遇即区间遍历结束后，将该区间内可达的最远距离maxPos作为下一次跳跃的区间右端点 r ，此时跳跃一步
当 r 可以到达边界时，即结束遍历
时间复杂度O(n)

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = 0;
        int maxPos = 0;
        int step = 0;
        while(r < n-1){
            maxPos = Math.max(maxPos, l + nums[l]);
            // 该区间已遍历结束，更新区间右端点，此步跳出
            if(l == r){
                r = maxPos;
                step ++;
            }
            l ++;
        }
        return step;
    }
}