地址

https://leetcode-cn.com/problems/jump-game-ii/

描述

思想

//在当前可达的范围内寻找下一跳可以到达的最远位置

代码

y总的

class Solution {
public:
    int jump(vector<int>& nums) {
        const int n = nums.size();
        vector<int> f(n);
        f[0] = 0;
        int last = 0;

        for (int i = 1; i < n; i++) {
            // 依次求 f[i] 的值。
            while (i > last + nums[last]) // 根据 i 来更新 last。
                last++;

            f[i] = f[last] + 1; // 根据 f[last] 更新 f[i]。
        }

        return f[n - 1];
    }
};

自个想的

class Solution {
public:
    int jump(vector<int>& nums) {
        //在当前可达的范围内寻找下一跳可以到达的最远位置
        int num=0,l=nums.size();
        if(l==1) return num;
        for(int i=0;i<nums.size();){
            int max=0,pos=0;
            int jump=nums[i];//在该位置可以跳跃的最大长度
            if(i+jump>=l-1) {num++;return num;}
            else num++;
            for(int j=i+1;j<=i+jump;j++){
                int jump2=nums[j];
                if(j+jump2>=l-1) {num++;return num;}
                if(j+jump2>max){
                    max=j+jump2;
                    pos=j;
                }
            }
            i=pos;
        }
        return -1;
    }
};