0045.跳跃游戏 II

方法一：动态规划

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

func jump(nums []int) int {
	dp, n := make([]int, len(nums)), len(nums)
	for i := 1; i < n; i++ {
		dp[i] = 10000
		for j := 0; j < i; j++ {
			if i-j <= nums[j] {
				if dp[i] > dp[j]+1 {
					dp[i] = dp[j] + 1
				}
			}
		}
	}
	return dp[n-1]
}

方法二：贪心算法

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func jump(nums []int) int {
	maxDistence, step, end := 0, 0, 0
	for i := 0; i < len(nums)-1; i++ {
		if i+nums[i] > maxDistence {
			maxDistence = i + nums[i]
		}
		if i == end {
			step, end = step+1, maxDistence
		}
	}
	return step
}