c - 到达终点所需的最小跳跃次数的线性时间算法

Question

问题:到达终点的最小跳跃次数

给定一个整数数组，其中每个元素代表可以从该元素向前移动的最大步数。编写一个函数返回到达数组末尾(从第一个元素开始)的最少跳转次数。如果某个元素为 0，则我们无法移动该元素。

例子:

输入:arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}输出:3(1-> 3 -> 8 ->9)第一个元素是 1，所以只能走到 3。第二个元素是 3，所以最多可以走 3 步，即到 5 或 8 或 9。

来源:http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

我已经制定了一个线性时间算法来查找到达数组末尾所需的最小跳跃次数。

源码如下:

int minJumpsUpdated(int arr[], int n)
{
  int *jumps = malloc(n * sizeof(int));  // jumps[n-1] will hold the result
  int i =1, j = 0;

  jumps[0] = 0;
  for (i = 1; i < n; ) { 

    // if i is out of range of arr[j], then increment j
    if (arr[j] + j < i && j < i) {

      j++;

    // else if i is within range of arr[j], 
    //   jumps for ith element would be jumps[j]+1
    } else if (arr[j] + j >= i && j < i) {

      jumps[i] = jumps[j] + 1;
      i++;

    } else {
      printf("solution does not exist");
      return -1;
    }
  }

  printf("jumps: ");
  for (i = 0; i < n; i++) {
    printf("%d, ", jumps[i]);
  }
  return jumps[n - 1];
}

例子:

1.) 最初 i=1, j=0和 arr[] = {1, 3, 6, 1, 0, 9};

jumps[] = 0,0,0,0,0,0

2.) 作为i在 arr[j] 范围内IE。 i<= j+arr[j] ，到达第 i 个位置所需的跳跃次数将是到达第 j 个位置的最小跳跃次数 + 1。

i=2, j=0, jumps[] = 0,1,0,0,0,0

3.) i>j+arr[j]即 j++;

i=2, j=1, jumps[] = 0,1,0,0,0,0

4.) i<=j+arr[j]即 jumps[i] = jumps[j]+1;

i=3, j=1, jumps[] = 0,1,2,0,0,0

5.) i<=j+arr[j]即 jumps[i] = jumps[j]+1;

i=4, j=1, jumps[] = 0,1,2,2,0,0

6.) i<=j+arr[j]即 jumps[i] = jumps[j]+1;

i=5, j=1, jumps[] = 0,1,2,2,2,0

7.) i>j+arr[j]即 j++;

i=5, j=2, jumps[] = 0,1,2,2,2,0

8.) i<=j+arr[j]即 jumps[i] = jumps[j]+1;

i=6, j=2, jumps[] = 0,1,2,2,2,3

------ 结束 ------

我无法确定该程序在哪个测试用例下无法运行。我问这个是因为在互联网上优化的解决方案使用的是 O(n^2) 的 DP。我的解决方案是线性时间。即 O(n)。所以我假设有一些情况是这个算法无法处理的。所以我很好奇它不处理什么情况。

您的帮助将不胜感激。

谢谢。

Answer 1

算法总结:

1. 拿起第一个元素，看看你能用它走多远
   (递增 i 直到 arr[j]+j < i )
2. 转到您可以从第一个项目到达的下一个项目，这至少会将您带到 i第一项。
3. 重复此操作，直到到达最后一个条目。

首先:
是的，它在 O(n) 中运行因为算法同时推送 i一个j只有一次来自 1至 n在最坏的情况下。

第二
我还没有看到 O(n²) 的证据是最佳时间复杂度。

第三种
您可以想象 arr像这样 所以这正是您的算法所做的。您可以使用它通过归纳法证明您的算法是正确的。但正如@Leo 提到的，必须有一个解决方案。

修复无解决方案
确保 j < i持有。