如何运用贪心思想玩跳跃游戏 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何运用贪心思想玩跳跃游戏

评论礼仪 见这里，违者直接拉黑。

[lingshaofu]

跳跃游戏 I 有瑕疵吧，【2，0，0】这个用例有问题

[ththth888]

循环的截止条件是n-1而不是n

[chenggiant]

[Jump Game II]用BFS来解也是不错

[labuladong]

测试了一下，直接复制我的代码都可以通过的，可能是你们写错了

[deepbreath373]

文中i是0 ~ n-1，精妙精妙！

[chenxiiang]

因为是要到达n-1的位置，所以n-1的元素实际上是没用的，我第一次就跳这个坑去了

[taoziganbei]

贪心策略：每次在能到达的所有位置中，选择下一步跳跃能到达的最远位置

[zhongweiLeex]

1. 提示：

提示 ：本题中 i 一直在是逐步往前的哦， 不是 一下子更新到最远位置的， 可以想象成 i 一直在追逐 farest 这个最远索引。

2. 使用dp数组的动态规划方法

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        //dp[i] 表示从0 跳到 i 坐标 至少需要多少步
        //最终需要求 dp[n-1] 即 从 0 跳到 n-1 至少需要多少步
        int[] dp = new int[n];
        //base case
        for(int i = 1; i< n;i++){
            dp[i]=n;
        }
        dp[0] = 0;
        for(int i = 1; i<n;i++){
            for(int j = 0;j<i;j++){
                if(j+nums[j]>= i){//如果当前所在位置的index  + 其最远能跳的距离超过了 想要跳到的坐标i则可以更新 dp[i]
                    dp[i] = Math.min(dp[i],1+dp[j]);
                }
            }
        }
        return dp[n-1];
    }
}

[Alwin4Zhang]

45. 跳跃游戏 II python versions

dp动态规划 勉强通过，没有超时

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        # dp[i]表示从开头0位置到当前i的最小步数
        for i in range(1, n):
            sub_problems = []
            for j in range(0, i):
                if i - j > nums[j]:  # 有一个数组比较长的case不用这个会超时
                    continue
                # if i - j <= nums[j]:
                sub_problems.append(dp[j] + 1)
            dp[i] = min(sub_problems)
        return dp[-1]

[861130245]

贴波自己写的贪心

int jump(vector<int>& nums) {
        int index = 0, res = 0, n = nums.size();

        // 当前位置不是最后一个时
        while (index < n - 1) {
            // 当前位置能一次跳到最后一个则返回
            if (index + nums[index] >= n - 1) {
                return res + 1;
            } else {
                // 选在自己能跳到的范围中, 选下一次能跳最远的
                int mostFar = index + 2;
                int nextIndex = index + 1;
                for (int i = 1; i <= nums[index]; i++) {
                    if (mostFar < index + i + nums[index + i]) {
                        mostFar = index + i + nums[index + i];
                        nextIndex = index + i;
                    }
                }
                index = nextIndex;
                res++;
            }
        }
        return res;
    }

[lzh2580]

i < n-1 充分利用了题目的条件，假设能到最后。真特么我还特意加了一个end == n-1的判断，画蛇添足

[cheng-miao]

daka

[Maxiah]

讲的真的很明白，举一反三

[Plasticine-Yang]

跳跃游戏Ⅱ TypeScript贪心解法

/**
 * @description 贪心选择
 */
function jump(nums: number[]): number {
  const n = nums.length;
  // 当前可跳跃范围的终点
  let end = 0,
    // 总共的跳跃次数
    jumps = 0,
    // 可到达的最远地方
    farthest = 0;

  // 遍历所有选择
  for (let i = 0; i < n - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    // 当前的可跳跃范围遍历结束 进入下一个可跳跃范围
    if (i === end) {
      // 每遍历完一个可跳跃范围就相当于做了一次决策
      // 总跳跃次数增加一次
      jumps++;
      // 更新下一次可跳跃范围的终点
      end = farthest;
    }
  }

  return jumps;
}

[dreamyang-liu]

这个每次end 感觉有些像二叉树层序遍历中每层开始时 获取当前queue的size，都是用来圈定处理范围

[deepbreath373]

check in

[zhongweiLeex]

改了遍历终点
添加了注释 ， 可能更好理解一点

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        if(len == 1) return 0;
        int curEnd = 0;
        int nextEnd = 0;
        int step = 0;
        for(int i = 0; i< len ; i++){
           // 下次能到的最大位置
            nextEnd = Math.max(nextEnd, nums[i] + i);
            if(nextEnd >= len-1){
                return step+1;
            }
            //到达预估最大位置， 则跳到下一个位置
            if(i == curEnd){
                step++;
                curEnd = nextEnd;
            }
        }
        return step;
    }
}

[czhongwe]

我现在看啥都是树....

public boolean canJump(int[] nums, int curIndex) {
        if (nums[curIndex] == 0 && curIndex < nums.length - 1) {
            return false;
        } else if (nums[curIndex] >= nums.length - 1 - curIndex) {
            return true;
        }
        int num = nums[curIndex];
        boolean flag = Boolean.FALSE;
        for (int i = 1; i <= num; i++) {
            flag = flag || canJump(nums, curIndex + i);
        }
        return flag;
    }

[labuladong]

这说明已经上道了👍

[GXhunter]

贪心什么的我真不会，来个动态规划 搞一下

    public int jump(int[] nums) {
        int n = nums.length;
//        dp[i] 第i个位置开始，跳到最后位置 最少需要的步数
        int[] dp = new int[n];
        Arrays.fill(dp, n);
//        base case
        dp[n - 1] = 0;
        if (n < 2) {
            return dp[0];
        }
        for (int i = n - 2; i >= 0; i--) {
//            转移方程 dp[i] = min(dp[i+1],...dp[i+nums[i]])+1
            for (int j = i + 1; j <= nums[i] + i && j < n; j++) {
                dp[i] = Math.min(dp[j] + 1, dp[i]);
            }
        }
        return dp[0];
    }

[labuladong]

直接动态规划暴力穷举也是可以的，就是效率低些

[yonggui-yan]

打卡打卡

[SUN7700]

跳跃游戏1中，为什么i <n - 1, 因为是判断终点前一个位置的farthest，例如arr = 【1，2，3，4，5】，是判断你走到 arr[3]（=4）时 farthest是否 >= 4 也就是 farthest >= n - 1;
如果你想使用 i < n 这个判断条件循环，就不能在 farthest <= i 时 return false, 因为i 可能等于 n - 1 就是走到了终点，我是在这里进行了break, 结尾语句还是：return farthest >= n -1

var canJump = function(nums) {
       let n = nums.length
       let farthest = 0
      for(let i = 0; i < n; i++) {
            farthest = Math.max(farthest, i + nums[i])
            if(farthest <= i) break
      }
      return farthest >= n - 1
};

[syumet]

II题用BFS的话其实就是在数层数，达到终点後返回所在层，而贪心的jumps也是在数层数，end则直接界定了每一层的界限，比BFS棋高一着

[lpdswing]

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_i = 0
        n = len(nums)
        for i, step in enumerate(nums):
            if max_i >= i and i + step > max_i:
                max_i = i + step
                if max_i >= n-1:
                    return True
        return max_i >= n-1

55这样效率更高一点

[cuixuage]

45题，跳跃游戏，动态规划。 通过全部Leetcode测试用例。
思路: 从后向前遍历，dp[i] = 1 + std::min(dp[i+1], dp[i+2].....,dp[i+nums[i]]

    int DP_jump(vector<int>& nums) {
        vector<int> dp(nums.size(), nums.size());
        // base case
        if (nums.size()==0 || nums.size()==1) return 0;
        dp[nums.size()-1] = 0;
        // 从后向前遍历
        for (int i=nums.size()-1; i>=0; i--) { 
            int min_jump = dp[i];
            for(int j=1; j<=nums[i]; j++) {
                int end = i+j;  //可到达的所有位置
                if (end < nums.size()) {
                    min_jump = std::min(min_jump, dp[end]+1);
                }
            }
            dp[i] = min_jump;
        }
        return dp[0];
    }

[Jeffzholy]

是不是可以这么理解最后举的贪心的例子，我分享下自己的思路。假设跳到位置3（元素值为2的位置），之后有一条路可以用最少的步数到达最后，那么跳到位置2（元素值为4的）一定也可以，因为这个位置上覆盖的范围更远，是可以在下一步选择那条最少的步数的，所以贪心方法成立（至少不会比那个最优的差，也即是最优的）

[felixie99]

我觉得思路应该是：
想要步数最少，那么肯定每次选能跳最远的
假设跳到位置3，那么我们就标记end为位置3，再在i 和 end中间， 选取下一次跳的最远的距离

[Debug-Lee]

第一个问题，结尾是不是可以直接返回 true，不用 farthest >= n - 1 判断了。上面已经判断循环过程中没有遇到0了，说明前0 - n-2个元素都可以到达，且每个元素都不为0，那最后一个元素就一定可以到达。

[WeihuaZhu]

第一问感觉判断条件变成对于每个i 判断不能到达i会更好理解一些，和作者的答案是等效的：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if not nums:
            return False
        farthest = 0
        for i in range(len(nums) - 1):
            # cannot reach position i
            if farthest < i:
                return False
            farthest = max(farthest, i + nums[i])
        return farthest >= len(nums) - 1

[marcmk6]

原来第二题线性复杂度就能搞定了，我还变成视频片段拼接问题做的😅

[gostudying]

func jump(nums []int) int {
	n := len(nums)
	// dp[i]表示从i位置跳到最后一格最少需要的步数
	dp := make([]int, n)
	// base case
	dp[n-1] = 0
	for i := n - 2; i >= 0; i-- {
		// 此处不能使用最大int值，因为后面有1+min可能导致整型溢出
		min := 99999
		// 动态方程：dp[i]=1+min(p[i+1...i+nums[i]])
		for j := i + 1; j <= i+nums[i] && j < n; j++ {
			min = int(math.Min(float64(min), float64(dp[j])))
		}
		dp[i] = 1 + min
	}
	return dp[0]
}

[gostudying]

用dp数组可能比dp函数好理解一点

[mengfanxiao777]

res = min(subProblem + 1, res);这里的 +1是为什么呀，不太理解，有大佬解答一下吗？

[zixingkong]

这里dp(nums,p)指的应该是从索引位置p跳跃到最后所需要的最少跳跃数，而不是最小步数，因为dp(nums,p)到dp(nums,p+i)多跳跃了1次，所以有dp(nums,p)=min(dp(nums,p+i)+1)

[lisgroup]

原文中的这句 “通过备忘录 memo 消除重叠子问题，取其中的最小值最为最终答案：” 多了一个字，“最”，应该是 “取其中的最小值为最终答案”。

[CarlLy7]

打卡，附上详细注解的Java代码

    public int jump(int[] nums) {
        int n= nums.length;
        //end代表当前这个位置可以跳跃到的最远的位置的下标
        //forest是可以跳跃到的最远的距离
        int end=0,forest=0;
        //res记录跳跃的次数
        int res=0;
        //依然是跳跃到最后一个位置就结束了
        for (int i = 0; i < n-1; i++) {
            //forest是当前这个下标作为开始起点，可以跳跃到的最远的位置
            forest=Math.max(forest,nums[i]+i);
            //当i往后移动到了当前这个位置可以跳跃到的最远的位置的时候肯定要进行一次选择进行跳跃，所以跳跃次数加一，
            // 然后下次进行跳跃选择的边界是可以当前这次跳跃可以到达的最远位置
            if (i==end){//这里i==end的时候说明我们的i后移已经到了可以跳跃的最远位置，我们必须做出一次跳跃选择了
                res++;
                end=forest;
            }
        }
        return res;
    }