[数据结构与算法]贪心算法——跳跃游戏ii

45. 跳跃游戏 II
    给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

题目来源：力扣
网址：https://leetcode-cn.com/problems/jump-game-ii/

第一种方法，回溯，深度优先搜索遍历，但是被判超时。

我们从第一个选择，通过选择的第一个数，对之后的指定的范围进行尝试，也就是全部尝试一遍，找到最少次数的跳跃。

dfs深度优先搜索

var mpathl int
func jump(nums []int) int {
    if len(nums) == 1 {
        return 0
    }
//    nums = append(nums , 1 << 31 - 1)
//    fmt.Println(nums)
    mpathl = 1 << 31 - 1
    path := make([]int , 1)
    path[0] = nums[0]
    backtrace(nums , 0 , path)
    return mpathl
}

func backtrace (nums []int , n int , path []int) {
    if n == len(nums) - 1{
        //fmt.Println(path)
        if len(path) - 1< mpathl {
            mpathl = len(path) - 1
        }
        return
    }
    // fmt.Println(path)
    // mpathl = len(path)
    for i := n + 1 ; i <= min(nums[n] + n , len(nums) - 1) ; i ++ {
        backtrace(nums , i , append(path , nums[i]))
    }
}

func min (m ,n int) int {
    if m < n {
        return m
    } else {
        return n
    }
}

贪心

在目标范围内，选择可以向后走最大的数字，然后在指定范围内选择向后走最大范围的数字，直到最大范围 覆盖到末尾。

func jump(nums []int) int {
	if len(nums) <= 2 {
		return len(nums) - 1
	}
	if nums[0] >= len(nums)-1 {
		return 1
	}
	maxvalue := nums[0]
	maxindex := 0
	step := 1
	for true {
		max := nums[maxindex+1]
		maxi := maxindex + 1
		for k := maxindex + 2; k <= min(maxvalue+maxindex, len(nums)-1); k++ {
			if max-nums[k] <= k-maxi {
				max = nums[k]
				maxi = k
			}
		}

		maxvalue = max
		maxindex = maxi
		step++
		if max+maxi >= len(nums)-1 {
			break
		}
	}
	return step
}

func min(m, n int) int {
	if m < n {
		return m
	} else {
		return n
	}
}