达到最后一个索引所需的最小步骤数

Question

给定一个非负整数数组，您最初位于数组的第一个索引处。

数组中的每个元素表示该位置的最大跳跃长度。

您的目标是以最少的跳跃次数达到最后一个索引。

例如：给定数组A=[2,3,1,1,4]

到达最后一个指数的最小跳跃次数为2次。（从索引0跳转1步到1，然后3步到最后一个索引。）

我已经从左到右构建了一个dp[]数组，以便dp[i]指示从arr[0]到达arr[i]所需的最小跳转次数。最后，我们返回dp[n-1]。

我的代码的最坏情况时间复杂度是O（n^2）。

这可以在更好的时间复杂度下完成。

本题抄袭自leetcode。

Answer 1

我认为，你可以用这些技术来提高计算动态：
你花O（N）来计算当前d[i]。但是你可以用d[j]保持一个集合，其中j=0... i-1。现在你只需要使用二进制搜索来查找：

这样的d[j]是所有（0..i-1）中最小的，并且从j位置i-pos是可到达的。

Answer 2

可以使用范围最小段树来解决此问题。段树是一种数据结构，允许您维护值数组，还可以查询数组子段上的聚合操作。更多信息可在此处找到：https://cses.fi/book/book.pdf（第9.3节）

您将在段树中存储值d[i]，d[i]是从索引i开始时到达最后一个索引所需的最小步骤数。显然，d[n-1]=0。一般来说：

d[i]=1分钟（d[i 1]，…，d[min（n-1，i a[i]）），

因此，您可以通过反向计算d中的所有值，并在每个步骤后更新段树。最终的解决方案是d[0]。由于段树的更新和查询都在O（logn）中工作，所以整个算法都在O（nlogn）中工作。

Answer 3

int jump(vector<int>& a) {
    int i,j,k,n,jumps,ladder,stairs;
    n = a.size();
    if(n==0 || n==1)return 0;
    jumps = 1, ladder = stairs = a[0];
    for(i = 1; i<n; i++){
        if(i + a[i] > ladder)
        ladder = i+a[i];
        stairs --;
        if(stairs + i >= n-1)
        return jumps;
        if(stairs == 0){
            jumps++;
            stairs = ladder - i;
        }
    }
    return jumps;
}