Dynamic Programming in Data Structures MCQ question and answer with solution

length     price
    1	           2
    2             5
    3	           6
    4	           9
    5	           9
    6	          17
    7 	          17	
    8	          18
    9	          20
   10	          22

#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;
}

#include<stdio.h>
int main()
{
      int coins[10]={1,3,4},lookup[100];
      int i,j,tmp,num_coins = 3,sum=10;
      lookup[0]=0;
      for(i=1;i<=sum;i++)
      {
	    int min_coins = i;
	    for(j=0;j<num_coins;j++)
	    {
	         tmp=i-coins[j];
	         if(tmp<0)
	          continue;
	         if(lookup[tmp] < min_coins)
		 min_coins=lookup[tmp];
	    }
	    lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

#include<stdio.h>
int get_min(int a, int b)
{
     if(a<b)
        return a;
     return b;
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
      int t1[n], t2[n],i;
      t1[0] = entry[0] + spent[0][0];
      t2[0] = entry[1] + spent[1][0];
      for(i = 1; i < n; i++)
      {
          t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
          t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]);
      }
    return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}
int main()
{
     int time_to_reach[][3] = {{6, 1, 5},
                            {2, 4, 7}};
     int time_spent[][4] = {{6, 5, 4, 7},
                        {5, 10, 2, 6}};
     int entry_time[2] = {5, 6};
     int exit_time[2] = {8, 9};
     int num_of_stations = 4;
     int ans = minimum_time_required(time_to_reach, time_spent, 
               entry_time, exit_time, num_of_stations);
     printf("%d",ans);
     return 0;
}

#include<stdio.h>
int get_min(int a, int b)
{
     if(a<b)
        return a;
     return b;
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
     int t1[n], t2[n],i;
     t1[0] = entry[0] + spent[0][0];
     t2[0] = entry[1] + spent[1][0];
     for(i = 1; i < n; i++)
     {
         t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
         t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]);
     }
     return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}
int main()
{
    int time_to_reach[][3] = {{6, 1, 5},
                           {2, 4, 7}};
    int time_spent[][4] = {{6, 5, 4, 7},
                        {5, 10, 2, 6}};
    int entry_time[2] = {5, 6};
    int exit_time[2] = {8, 9};
    int num_of_stations = 4;
    int ans = minimum_time_required(time_to_reach, time_spent, 
              entry_time, exit_time, num_of_stations);
    printf("%d",ans);
    return 0;
}