45. Jump Game II

#Array#Dynamic Programming#Greedy

Вам дан 0-индексированный массив целых чисел numsдлины n. Изначально вы находитесь в позиции nums[0].

Каждый элемент nums[i]представляет максимальную длину прыжка вперед от индекса i. Другими словами, если вы находитесь в nums[i], вы можете перейти в любое nums[i + j]место:

• 0 <= j <= nums[i]и
• i + j < n

Верните минимальное количество прыжков для достиженияnums[n - 1] . Тестовые случаи генерируются таким образом, чтобы вы могли достичь nums[n - 1].

Пример 1:

Ввод: nums = [2,3,1,1,4]
Вывод: 2
Пояснение: Минимальное количество прыжков для достижения последнего индекса равно 2. Прыгните на 1 шаг от индекса 0 к 1, затем на 3 шага к последнему индексу.

Пример 2:

Ввод: числа = [2,3,0,1,4]
Вывод: 2

Ограничения:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• Гарантированно, что вы сможете достичь nums[n - 1].

Пример решения на go

func jump(nums []int) int {

var index int

var count int

var check int

for index<len(nums)-1 {

far := 0

for i := check; i <= index; i++ {

far = max(far, i+nums[i])

}

check = index + 1

index = far

count++

}

return count

}

func max(a, b int) int {

if a > b {

return a

}

return b

}