0

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

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

输出：2

解释：到达索引 4 的最短路径是索引 0 -> 索引 1 -> 索引 4，需要 2 次跳转。

以下是解决方案：

// 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。记忆后我无法弄清楚解决方案的时间复杂度。有人可以帮助我估计上述解决方案的时间复杂度。

4

2 回答 2

1

我有一种方法可以解决这个O(nlogn)复杂的问题（也许会有更好的方法）

l,r使用惰性段树来存储索引的最小值。

在每个索引集上dp[i] = query(i,i)，然后update(i+1,dp[i]+i,dp[i]+1)

如果您感到困惑，请发表评论。我也会提供实施。

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

于 2020-03-22T15:45:33.163 回答
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)）。

可以证明，该算法使用数学归纳法找到了最小的跳跃次数。

于 2020-03-22T17:14:13.610 回答