跳跃游戏

1. 题目描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标

2. 思路

1. 思路一
   • 暴力DFS
   • 当前索引从0开始，尝试让当前索引加上0...nums[index]
   • 是否能超过len(nums)
2. 思路二
   • 最远位置

3. 实现

3.1. 暴力DFS

func canJump(nums []int) bool {
    return canJumpDFS(nums, 0)
}

func canJumpDFS(nums []int, index int) bool {
    if index >= len(nums) -1 {
        return true
    }
    steps := nums[index]
    if steps == 0 {
        return false
    }

    for i := steps; i > 0; i-- {
        if canJumpDFS(nums, index+i) {
            return true
        }
    }

    return false
}

3.2. 暴力DFS+缓存

func canJump(nums []int) bool {
    memo := make(map[int]bool, 0)
    return canJumpDFS(nums, 0, memo)
}

func canJumpDFS(nums []int, index int, memo map[int]bool)bool {
    res, ok := memo[index]
    if ok {
        return res
    }

    if index >= len(nums)-1 {
        memo[index] = true
        return true
    }

    step := nums[index]
    for j := step; j > 0;j--{
        if canJumpDFS(nums, index+j, memo){
            memo[index+j] = true
            return true
        }
    }


    memo[index] = false
    return false
}

3.3. 最远位置

func canJump2(nums []int) bool {
	//初始化当前能到达最远的位置
	maxIndex := 0
	//i为当前位置，step是当前位置的跳数
	index := 0
	step := 0
	for index, step = range nums {
		//如果当前位置能到达，并且当前位置+跳数>最远位置
		nextMaxIndex := index + step
		if maxIndex >= index && nextMaxIndex > maxIndex {
			//更新最远能到达位置
			maxIndex = nextMaxIndex
		}
	}

	return maxIndex >= index
}

4. 参考

• 55. 跳跃游戏 - 力扣（LeetCode）