link
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i j] 处:
- 0 <= j <= nums[i]
- i j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
Example 1:
代码语言：javascript复制Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.func jump(nums []int) int {
// 动态规划四步走：
// 1、状态：f[i] 表示从起点到当前位置跳的最小次数
// 2、推导：f[i] = min(f[j] 1),a[j]) j >=i 表示从j位置用一步跳到当前位置，这个j位置可能有多个，取最小的一个就行
// 3、初始化：f[0] = 0
// 4、结果：f[n-1]
f := make([]int, len(nums))
f[0] = 0
for i := 1; i < len(nums); i {
// f[i] 先取一个默认最大值i
f[i] = i
// 遍历之前结果取一个最小值 1
for j := 0; j < i; j {
if nums[j] j >= i {
f[i] = min(f[j] 1,f[i])
}
}
}
return f[len(nums)-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}贪心
设每次所选的起跳位置为start，
能到的最大距离end为i nums[start]，
我们为了能用最小的次数跳到终点，每次都想跳到最大的位置为max。
跳的次数为count
为了保证count最小，所以每次跳都要这一跳能跳的最远位置，解题思路应为贪心算法。从前向后遍历，
每完成一次跳跃后更新count与end的值，下一次的i即从上一跳的最远处end_{i-1}(=start_i)endi−1(=starti)开始计算，
遍历位置start_istarti到end_iendi得到能跳的最远处max，然后当遍历到end_iendi时，更新下一跳的起点start_{i 1}starti 1为max
代码语言：javascript复制func jump(nums []int) int {
if nums == nil || len(nums) == 0{
return -1
}
n := len(nums)
count,max,end := 0,0,0
for i:=0;i<n-1;i {
// 记录每一个位置i所能跳到的最大位置max
if i nums[i]>max{
max = i nums[i]
}
// end是上一个所选的起跳位置能跳的最远处，当到达end时，更新下一跳的最大位置
if i == end{
end = max
count
}
}
return count
}
