跳跃游戏 II

 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 }; 

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; 
    } 
};