Saturday, September 3, 2011

Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array

Given an array of integers, each element represents the max number of jumps can make forward. 
What is the minimum number of element selections to reach the end of the array (starting from the first element) ?

Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps

Implementation  : Using Dynamic programming - 

int find_min_steps(int arr[], int n)
{
  // min_steps_dp[i] is an array which 
  // indicate minimum jumps required to reach i. 
  int min_steps_dp[20];
  int i, temp, next_vacant;
  // next_vacant : Is the index in the array whose min_steps needs to be updated
  // in the next iteration.
  next_vacant = 1;
  for(i=0;i= n)
    {
      min_steps_dp[n-1] = min(min_steps_dp[n-1],min_steps_dp[i] +1);
    }
    else
    {
      min_steps_dp[temp] = min(min_steps_dp[temp],min_steps_dp[i]+1);
    }
    if(temp>next_vacant)
    {
      for(;next_vacant<temp;next_vacant++)
      {
      // this loop executes only ONCE for each element in the array, so over the
      // course of execution, is an O(n) loop only. 

        min_steps_dp[next_vacant] =min(min_steps_dp[next_vacant],min_steps_dp[temp]);
      }
    }
  }
  for(i=0;i<n;i++)
  {
    printf("%d ",min_steps_dp[i]);
  }
  return min_steps_dp[n-1];
 
}
main()
{
  int arr[] = {1,3,5,8,9,2,6,7,6,8,9};
  int len;
  len = sizeof(arr)/sizeof(arr[0]);
  printf("\n MIN steps : %d\n",find_min_steps(arr,len));
}

1 comment:

  1. What is the Best Coin Casino in the United States? - Casinoworld
    Best Coin Casino: The Best No Deposit Casinos in the USA · $25 No Deposit Bonus at DraftKings · $10 Free for $25 on Signup · $10 Free on Signup

    ReplyDelete