题目描述
解题思路
贪心解法
从起点开始找到他能到达的点中，可以跳的最远的点。举个例子，起点是sx，可以到达位置s1, s2,其中s1可以跳step1，s2可以跳step2,那么取s1+step1，s2+step2中的最大值，代表可以下一跳可以到达的最远的地方。依次贪心，保证最后结果最优。
代码实现
class Solution {
public:
int jump(
vector<int>& nums) {
int n = nums.size();
if(n ==
1)
return 0;
int l = nums[
0];
int start =
0;
int sum =
1;
int Max =
0;
while(l < n-
1)
{
for(
int i = start+
1; i <= l && i < n; i++)
{
if(nums[i]+i > Max)
{
Max = nums[i]+i;
start = i;
}
}
l = Max;
sum++;
}
return sum;
}
};
