最小跳转数组（自上而下的方法）

Question

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

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

输出：2

说明：到达索引4的最短方法是索引0->索引1->需要2次跳转的索引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）解决方案：