最小跳跃阵列(自上而下的方法)

Question

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

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

输出：2

说明：到达索引4的最短方法是索引0->索引1->索引4，需要两次跳跃。

以下是解决方案：

// 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(nlogn)复杂性中的这个问题(也许有更好的方法(

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

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

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

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

Answer 2

不确定你的问题，但我想我有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((。

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