最小跳跃数组（自顶向下方法）

Question

问题陈述：给定一个长度为N的非负整数数组A，您最初位于数组的第一个索引处。数组中的每个元素表示该位置的最大跳跃长度。返回到达最后一个索引所需的最小跳转次数。

输入：A=[2,3,1,1,4]

产出：2

说明：达到指数4的最短途径是指数0-

以下是解决方案：

// M is the function that gives the required minimum jumps
// nums is the vector containing jumps (here I have used nums in place of array A).
// start denoting the starting index
// map(m) STL for memoization

int M(vector<int> &nums, int start, unordered_map<int, int>&m){

    if(start == nums.size()-1){return 0;} // if we reach the last index then return 0.

    if(start >= nums.size()){return INT_MAX;} // if we reach beyond last index then return some big value that can't be the answer.

    if(nums[start] == 0){return INT_MAX;} // if in mid we get jump value = 0 then we cannot expect the min jump so again return some big value.

    if(m[start] != 0){return m[start];} // if we already stored the value (calculated the answer) then return stored value 

    int ans = INT_MAX; // assuming initially answer to be some big value. 

    for(int i=1; i<=nums[start]; i++){ // jump can be made from 1 to maximum value of that element in array i.e. nums[start]

        ans = min(ans, 1+M(nums, start+i, m)); // answer is minimum of previously calculated answer and 1 + allowed path (start + i).

        m[start] = ans; // storing it in map.
    }

    return m[start]; // returning the stored value
}

我得到了上述解决方案的TLE。我无法在记忆后计算出解决方案的时间复杂度。有人能帮我估计一下上述解决方案的时间复杂度吗。

Answer 1

我不确定你的问题，但我想我有一个O（N）解决方案：

int M(const vector<int> &nums)
{
    int n_jumps = 0;
    int cur_pos = 0;
    int prev_pos = 0;
    int next_jump = 0;
    int max_value = 0;
    int value;
    int i;
    while (cur_pos + nums[cur_pos] < nums.size() - 1)
    {
        next_jump = 0;
        max_value = 0;
        i = cur_pos > 0 ? prev_pos + nums[prev_pos] + 1 : 1;
        for (; i <= cur_pos + nums[cur_pos]; ++i)
        {
            value = i + nums[i];
            if (value >= nums.size() - 1) return n_jumps + 2;
            if (max_value < value)
            {
                max_value = value;
                next_jump = i - cur_pos;
            }
        }
        prev_pos = cur_pos;
        cur_pos += next_jump;
        ++n_jumps;
    }
    return n_jumps + 1;
}

每次我们通过最大限度地增加本回合和下一回合的距离来选择跳跃幅度。最后一次跳转可以是允许的最大跳转，即我们所在元素的值。

请注意，当我们跳转到下一个元素时，我们不必检查从上一个位置（给出O（N））可以访问的元素。

可以证明，该算法利用数学归纳法求出了最小跳数。

Answer 2

我在O（nlogn）复杂性中有一个解决这个问题的方法（可能会有更好的方法）

使用延迟段树存储l，r索引的最小值。

在每个索引集上dp[i]=查询（i，i）然后更新（i1，dp[i]i，dp[i]1）

如果你感到困惑，请发表评论。我也将提供实现。

我知道可能会有更好的解决方案，因为这个问题似乎很经典，但这是我第一次想到的。