Examveda

Consider the following dynamic programming implementation of the minimum jumps problem:
#include<stdio.h>
#include<limits.h>
int min_jump(int *arr, int len)
{
     int j, idx, jumps[len];
     jumps[len - 1] = 0;
     for(idx = len - 2; idx >= 0; idx--)
     {
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
		 if(jumps[idx + j] + 1 < tmp_min)
		     tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
     }
     return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%d\n",ans);
      return 0;
}
Which of the following "for" loops can be used instead of the inner for loop so that the output doesn't change?

A. for(j = 1; j < arr[idx] + len; j++)

B. for(j = 0; j < arr[idx] - len; j++)

C. for(j = idx + 1; j < len && j <= arr[idx] + idx; j++)

D. No change is required

Answer: Option D


Join The Discussion

Related Questions on Dynamic Programming in Data Structures