欢迎光临散文网 会员登陆 & 注册

贪心/dp | 跳跃游戏

2022-02-09 23:48 作者:剑离我离  | 我要投稿

跳跃游戏 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 ; }


贪心/dp | 跳跃游戏的评论 (共 条)

分享到微博请遵守国家法律