// the point of solving this kind of problem is that we should realize that
// their DP array(store minimum steps) must be like [0,1*,2*,3*,''',N*]
// (here * means one or more)
class Solution {
public:
int jump(vector<int>& nums)
{
unordered_map<int,pair<int,int>> map;
map[0] = pair<int,int>(0,0);
int step = 0;
while(true)
{
int start = map[step].first;
int end = map[step].second;
if(end==nums.size()-1)
{
return step;
}
int tmpEnd = -1;
for(int i = start;i<=end;i++)
{
tmpEnd = max(tmpEnd,nums[i]+i);
}
map[++step] = pair<int,int>(end+1,min(int(nums.size()-1),tmpEnd));
}
}
};
