通过最大跳跃长度数组的最短路径

Question

我正在调试以下问题并发布代码。不知道代码是否正确。我目前的疑问是，i是否应该一直增加（在这一行--for（；i

>

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

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

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

例如：给定数组A=[2,3,1,1,4]，到达最后一个索引的最小跳转次数为2。（从索引0跳转1步到1，然后3步到最后一个索引。）

class Solution {
public:
    int jump(vector<int>& nums) {
        int i = 0, n = nums.size(), step = 0, end = 0, maxend = 0;
        while (end < n - 1) {
            step++;
            for (;i <= end; i++) {
                maxend = max(maxend, i + nums[i]);
                if (maxend >= n - 1) return step;
            }
            if(end == maxend) break;
            end = maxend;
        }
        return n == 1 ? 0 : -1;
    }
};




Answer 1

我在分享算法。现在，做BFS描述如下：

int A[N];         // It contains the initial values
int result[N];    // Initialise all with positive infinty or INT_MAX in C
bool visited[N];  // Initially, all initialise with '0' means none of the index is visited
queue Q;          // create a queue 

index = 1
cost = 0
push index in rear of Q.
result[index] = cost
visited[index] = true

while(Q is not empty) {
    index = pop the value from the front of the Q.
    cost = cost + 1

    for(i in 1 to A[index]) {
        temp_index = index + i;
        if(temp_index <= N   AND  visited[temp_index] == false) {
            push temp_index in rear of Q.
            result[temp_index] = cost
            visited[temp_index] = true
        }
    }
}

// Finally print the value of result[N]
print result[N]

注：还存在一种DP方法，其时间复杂度为O（n²）。

Answer 2

我在这里看到两种解决方法。

您只需从索引0开始，对于每个索引i尝试跳转到1到a[i]前面的索引，同时保留最后一个索引的最佳结果。它具有很高的算法复杂度，因此只有在效率确实不相关或者n非常小的情况下才应该选择它。

算法如下所示：

int best = 2147483647;
vector<int> A;

void Jump(int index, int step)
{
    if (step > best)
    {
        // for positive values, if step > best we won't improve our result
        // avoid worthless calculations
        return; 
    }
    if (index == A.size() - 1)
    {
        if (step < best) best = step;
        return;
    }

    int maxJumps = A[index];
    for (int i = index; i <= min(index + maxJumps, A.size() - 1); i++) 
    {
        Jump(i, step + 1);
    }
}

int main()
{
    // read input
    Jump(0, 0);
}

对于您的情况，递归将这样进行：

Start from A[0] (equal to 2)                             step = 0
> A[0+1] with step+1 (equal to 3)                        step = 1
>> A[1+1] with step+1 (equal to 1)                       step = 2
>>> A[2+1] with step+1 (equal to 1)                      step = 3
>>>> A[3+1] with step+1 (equal to 4)                     step = 4
>>>>> End of array. Compare step(4), best (MAXINT)         best = 4
>> A[1+2] with step+1 (equal to 1)                       step = 2
>>>> A[3+1] with step+1 (equal to 4)                      step = 3
>>>>> End of array. Compare step (3), best (4)             best = 3
>> A[1+3] with step+1 (equal to 4)                       step = 2
>>>>> End of array. Compare step(2), best (3)              best = 2
> A[0+2] with step+1 (equal to 1)                        step = 2
>>> A[2+1] with step+1 (equal to 1)                       step = 3
>>>> A[3+1] with step+1 (equal to 4)                      step = 4
>>>>> End of array. Compare step(4), best(2)               best = 2

动态聪明高效

这种方法使用动态规划。让我们有一个与数组A长度相同的数组B。让B[i]表示“跳转到A[i]至少需要多少步”。如果我们知道B[i]，那么我们可以说我们可以跳到B[i]1的所有可能索引（从i1到iA[i]）。因此，您所需要的只是从0到N-1遍历数组并向前看，改进每个i到ia[i]的结果。

大概是这样的：

vector<int> A, B;
int n;

int main() 
{
    // read n; read A of size n
    B.reserve(n); // B should be the same size and initialized with zeroes (by default)

    B[0] = 0; // not obligatory, 0 by default, just for clearness
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j <= min(i + A[i], n - 1); j++)
        {
            // improve result if we weren't there yet or if we can come to A[j]
            // faster if we go from A[i]
            if (B[j] == 0 || B[i] + 1 < B[j]) 
                B[j] = B[i] + 1;
        }
    }
}

该算法将这样工作：

A = 2 3 1 1 4
B = 0 0 0 0 0

i = 0, improve 0+1, 0+2
B = 0 1 1 0 0

i = 1, improve 1+1, 1+2, 1+3
B = 0 1 2 2 2

i = 2, no improvements 
i = 3, no improvements

答案存储在B[n-1]中。我已经实现了一个工作的IDEOne演示。

Answer 3

假设给定的数组是A[1..n]。从第i个位置，你可以跳1或2或3。。。A[i]。您已经计算了所有j的结果

ans[i]=min(ans[i+j],ans[i]) where i+j<=n && j=1,2,...A[i]

这样你就可以计算一切。

O（n^2）时间复杂度。

您也可以在O（n）中计算它。从一个位置，您将始终移动到具有最高i A[i]值的位置。我的意思是假设你在jth的位置。然后，您将下一步移动到位置j，使得j A[j]为最大值。如果其中一个元素是最后一个元素，跳转到最后一个元素。否则，跳转到具有最大值j A[j]的元素。

O（n）溶液。。。

Jump     2 3 1 1 4
position 1 2 3 4 5
j+A[j]   3 5 4 5 9
         ^ . . . .
         . ^ . . .    
         . . . . ^  ---> so 2 jumps.. :)

   Jump     2 5 1 1 1 1 1 1
   position 1 2 3 4 5 6 7 8
   j+A[j]   3 7 4 5 6 7 8 9
            ^ . . . . . . .
            . ^ . . . . . .
            . . . . . . . ^  (Here it is giving 2 jumps)