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;}
}