leetcode-go/hard/45.go

package main

func jumpSlow(nums []int) (steps int) { // TLE?
	n := len(nums)
	if n == 0 {
		return
	}
	dist := make([]int, n)
	for i := range nums {
		for j := 1; j <= nums[i] && i+j < n; j++ {
			if dist[i+j] == 0 || dist[i] < dist[i+j] {
				dist[i+j] = dist[i] + 1
			}
		}
	}
	return dist[n-1]
}

func jump(nums []int) (steps int) {
	n := len(nums)
	if n <= 1 {
		return
	}
	stop, nextStop := nums[0], nums[0]
	for i := range nums {
		if nextStop < i+nums[i] {
			nextStop = i + nums[i]
		}
		if i == stop || i == n-1 {
			stop = nextStop
			steps++
		}
	}
	return
}

// func main() {
// 	n := []int{2, 3, 1, 1, 4}
// 	println(jump(n))
// 	n = []int{}
// 	println(jump(n))
// 	n = []int{2, 1}
// 	println(jump(n))
// 	n = []int{0}
// 	println(jump(n))
// }