45.M 跳跃游戏 II

Problem: 45. 跳跃游戏 II

思路

贪心算法。

考虑到一定能跳到最后一个位置，如果多个位置都可以跳到最后一个位置，能让步数最少的位置应该是离最后一个位置最远的位置。因此可以从左往右遍历，不断找第一个能跳到target的位置，直到达到数组的第一个位置。

Code

func jump(nums []int) int {
	target := len(nums) - 1
	steps := 0
	for target > 0 {
		for i := 0; i < len(nums); i++ {
			if i+nums[i] >= target {
				target = i
				steps++
				break
			}
		}
	}

	return steps
}