题目链接：
45.跳跃游戏
题目描述：
思路一（广度优先搜索算法BFS）
通过广度优先搜索算法寻找最短距离
代码实现：
class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();if(n<=1) return 0;vector<int> visited(n,0);queue<pair<int, int>> qu;qu.push({0,0});visited[0] = 1;int ans = 0;while(!qu.empty()){pair<int, int> cur = qu.front();qu.pop();int index = cur.first;int step = cur.second;for(int k = nums[index]; k>0; k--){// 跳跃k步if((k+index) >= n-1){ans = step+1;break;}else{if(visited[k+index] != 1){qu.push({k+index, step+1});visited[k+index] = 1;}}}if(ans!=0){break;}}return ans;}
};
思路二（贪心算法）
例如，对于数组 [ 2 , 3 , 1 , 2 , 4 , 2 , 3 ] [2,3,1,2,4,2,3] [2,3,1,2,4,2,3]， 初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。
代码实现：
class Solution {
public:int jump(vector<int>& nums) {int maxPos = 0;int n = nums.size();int end = 0;int step = 0;for(int i=0; i<n-1; i++){if (maxPos >= i){maxPos = max(maxPos, i+nums[i]);if(i==end){end = maxPos;step++;}}}return step;}
};
