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.

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

代碼如下：

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é)果是用時(shí)超時(shí)，需要進(jìn)行剪枝或?qū)ふ腋玫姆椒?p>
思路二：仔細(xì)分析題目發(fā)現(xiàn)，題目關(guān)心的是最少通過(guò)幾步達(dá)到，對(duì)于具體的到達(dá)選擇并不關(guān)心，并且必然會(huì)達(dá)到。所以可以將其轉(zhuǎn)換為廣度優(yōu)先算法模型，然后采用貪心原則進(jìn)行求解，
代碼如下：
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;    }};