LC45-hard

不停超出时间限制
本着dfs的思想去写 发现居然不是dfs
题目

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解1）
先随意写了个递归 时间限制不行，不能过 71/92
2）再加上剪枝 80 / 92

class Solution {
public:
    void jumppy(vector<int>& nums,int i,int res,int &minin,int a[]) {
        if(i>=nums.size()-1){
           if(res<minin){
                minin=res;
            }
            return ;
        }

        if(res>=minin-1)
            return ;//再进一步or没有路
        int tmp=nums[i];
        for(;tmp>0;tmp--){

            jumppy(nums,i+tmp,res+1,minin);

        }

        return;
    }

    
    int jump(vector<int>& nums) {
        int x=INT_MAX;
        jumppy(nums,0,0,x);
        return x;
    }
};

3)用数组存储 91/92 居然还没有过

class Solution {
public:
    int jumppy(vector<int>& nums,int i,int a[]) {
        if(i>=nums.size()-1){
            a[i]=0;
           return 0;
        }
        int tmp=nums[i];
        int min=INT_MAX;
        for(;tmp>0;tmp--){
            if(i+tmp<nums.size()){
                //这种情况下最小的
                int x=0;
                if(a[i+tmp]==-1){                    
                    int epp=jumppy(nums,i+tmp,a);
                    if(epp==INT_MAX)
                        x=INT_MAX;
                    else
                        x=epp+1;
                } 
                else
                    if(a[i+tmp]==INT_MAX)
                        x=a[i+tmp];
                    else
                        x=a[i+tmp]+1;
                if(x<min)
                    min=x;                
            }

        }
        a[i]=min;

        return min;
    }

    
    int jump(vector<int>& nums) {
        // int x=INT_MAX;
        int a[nums.size()];
        memset(a,-1,sizeof(a));
        jumppy(nums,0,a);
        return a[0];
    }
};

4）真正解法（但是写的时候踩了很多坑）
比如for(i=maxlen){maxlen=j} 重复赋值导致计算不对
还有数错坐标，for循环应该写<=写成<

假设每一步为一层
设置最远跳距离和对应节点，即为这一层所能到达的最远区域。
（就像有个人说的，是抽象的层次遍历）
最坏情况，遍历整个数组（都是1？？）O(N)

class Solution {
public:
   
    int jump(vector<int>& nums) {
        // int x=INT_MAX;
        if(nums.size()<=1)
            return 0;
        

        int res=1;
        // int i=0;
         int maxlen=nums[0];
         int maxint=0;  
        while(maxlen<nums.size()-1){               
                int omax=maxlen;
                int oint=maxint;
                for(int j=oint+1;j<=omax;j++){
                    if(j+nums[j]>maxlen){
                        maxlen=j+nums[j];
                        maxint=j;
                        // cout<<maxlen<<endl;
                        if(maxlen>=nums.size()-1)
                            return res+1;  
                    }
                }
            // cout<<"------------"<<endl;
            // cout<<maxlen<<endl;
                if(maxlen>=nums.size()-1)
                    return res;
                if(maxlen>omax)
                    res+=1;

        }
    
        return res;
    }
};