45. 跳跃游戏 II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

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

思路：按照贪心选择策略，每次选择[i…end]区间中最大的值（能跳的最远的值）

  1. //每步都挑跨越最远的步子，最后一个不用跳，因为一定要最后有路 
  2. // 因为跳跃次数的结果集是单调递增的，所以贪心思路是正确的
  4. //最优，贪心算法，时间On，空间O1;
  5. func jump(nums []int) int {
  6.     n := len(nums)
  7.     cur_pos := 0            //当前目标位置，  搜索区间[i... cur_pos]
  8.     step := 0                // 需要跳跃的次数
  9.     max_step := 0            // 能达到的最远距离
  11.     for i := 0; i < n-1; i++ {
  12.         max_step = max(max_step, nums[i] + i)        // 记录下一次可以跳跃的最远距离
  13.         if i == cur_pos {                            // 当i走到上次的最远距离的时候
  14.             cur_pos = max_step                // 再向前走 记录的下一次可以走的最远距离
  15.             step++
  16.         }
  17.     }
  18.     return step
  19. }
  21. func max(x, y int) int {
  22.     if x > y {
  23.         return x
  24.     }
  25.     return y
  26. }
//dp解法，时间为On^2，空间On
func jump(nums []int) int {
    n := len(nums)
    dp := make([]int, n)                        // dp[i] 表示从起点到当前位置最小次数

    dp[0] = 0
    for i := 1; i < n; i++ {
        dp[i] = i                                    // dp[i] 最大值为i

        for j := 0; j < i; j++ {
            if nums[j] + j >= i {
                dp[i] = min(dp[i], dp[j]+ 1)       // 遍历之前结果取一个最小值+1
            }
        }
    }
    return dp[n-1]
}

func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}