给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
解:
对于这道题，最先想到的是动态规划，从后面向前计算，这样就知道前一个的最优步数，不用重复计算。但面对某些测试用例情况下
会显示超时，以下为动态规划的方法
1 class Solution { 2 public: 3 int jump(vector<int>& nums) { 4 map<int,int> map_index_length; 5 map_index_length[nums.size()-1]=0; 6 for(int i=nums.size()-2;i>=0;i--) 7 { 8 int best_length=INT_MAX-1; 9 int step=1;
//step小于当前大小可以移动距离 10 for(int j=i+1;j<nums.size()&&step<=nums[i];j++,step++) 11 { 12 best_length=min(best_length,map_index_length[j]); 13 } 14 15 map_index_length[i]=best_length+1; 16 17 } 18 return map_index_length[0]; 19 } 20 };
后面看别人解法，因为可以跳跃的步数小于当前数字大小而不是等于，发现此题应该考察的是贪心的方法
只要选择当前范围内最大的能达到的数字跳跃即可(可能有点难理解，比如3，3，2，2，1，2第一步应该选滴4位数2，即范围内nums[i]+i最大的数)
class Solution { public: int jump(vector<int>& nums) { //转化问题为找到每个范围内的最大值 int step=0; //记录下一次最长能到的下标 int maxLength=0; // int end=0; for(int i=0;i<nums.size()-1;i++) { //寻找可以到的范围内最大的数 maxLength=max(maxLength,nums[i]+i); //所选点的全部范围走完
if(i==end) { end=maxLength; //保存此次范围内最远的坐标
step++; } } return step; } };
所选点的全部范围走完
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/17582.html