Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array rePResents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:Given array A = [2,3,1,1,4]

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.)

Note:You can assume that you can always reach the last index.

思路一：將所有的情況都考慮進去，基于遞歸進行暴力搜索

代碼如下：

class Solution {public:    void oneJump(vector<int>& nums,int& minJump,int& count,int& pos)    {        if(pos == nums.size()-1)        {            if(minJump > count)            {                minJump = count;                return;            }        }                    for(int i=pos+1;i<=pos+nums[pos];i++)        {            if(i>nums.size()-1)                return;            count++;            oneJump(nums,minJump,count,i);            count--;        }    }        int jump(vector<int>& nums) {        int minJump = 0x7fffffff;        int count = 0;        int pos = 0;        oneJump(nums,minJump,count,pos);        return minJump;        }};結(jié)果是用時超時，需要進行剪枝或?qū)ふ腋玫姆椒?p>
思路二：仔細分析題目發(fā)現(xiàn)，題目關心的是最少通過幾步達到，對于具體的到達選擇并不關心，并且必然會達到。所以可以將其轉(zhuǎn)換為廣度優(yōu)先算法模型，然后采用貪心原則進行求解，
代碼如下：
class Solution {public:    int jump(vector<int>& nums) {        if(nums.size() < 2)            return 0;                    int level=0,currentMax=0,nextMax=0;        int pos=0;        while(currentMax-pos+1>0)        {            level++;            for(;pos<=currentMax;pos++)            {                if(pos+nums[pos] > nextMax)                    nextMax = pos+nums[pos];                if(nextMax >= nums.size()-1)                    return level;            }            currentMax = nextMax;        }        return 0;    }};