45. 跳跃游戏 II

动态规划

从后往前考虑。

时间复杂度：O(N^2)
空间复杂度：O(1)

func jump(nums []int) int {
    count := 0
    r := len(nums) - 1

    for r > 0 {
        for i := 0; i < r; i++ {
            if nums[i] >= r - i {
                r = i
                count++
                break
            }
        }
    }

    return count
}

从前往后考虑。

时间复杂度：O(N)
空间复杂度：O(1)

func jump(nums []int) int {
    count := 0
    n := len(nums)
    maxPosition := 0
    end := 0
    // r := len(nums) - 1

	for i := 0; i < n - 1; i++ {
		maxPosition = max(maxPosition, i + nums[i])
		if i == end {
			end = maxPosition
			count++
		}
	}
    
    return count
}

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