Dynamic Programming in Data Structures MCQ question and answer with solution

#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
       if(a > b)
         return a;
       return b;
}
int rod_cut(int *prices, int len)
{
       int max_price = INT_MIN; // INT_MIN is the min value an integer can take
       int i;
       if(len <= 0 )
          return 0;
       for(i = 0; i < len; i++)
          // subtract 1 because index starts from 0
          max_price = max_of_two(prices[i] + rod_cut(prices,len - i - 1), max_price); 
       return max_price;
}
int main()
{
       int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 3;
       int ans = rod_cut(prices, len_of_rod);
       printf("%d",ans);
       return 0;
}

#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
      int arr[num_of_dice + 1][S + 1];
      int dice, face, sm;
      for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
      for(sm = 1; sm <= S; sm++)
           arr[1][sm] = 1;
      for(dice = 2; dice <= num_of_dice; dice++)
      {
          for(sm = 1; sm <= S; sm++)
          {
              for(face = 1; face <= num_of_faces && face < sm; face++)
                  arr[dice][sm] += arr[dice - 1][sm - face];
          }
      }
      return arr[num_of_dice][S];
}
int main()
{
      int num_of_dice = 3, num_of_faces = 4, sum = 6;
      int ans = get_ways(num_of_dice, num_of_faces, sum);
      printf("%d",ans);
      return 0;
}

#include<stdio.h>
int max_num(int a,int b)
{
      if(a> b)
	 return a;
      return b;
}
int maximum_subarray_sum(int *arr, int len)
{
      int sum[len], idx;
      sum[0] = arr[0];
      for(idx = 1; idx < len; idx++)
	 sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]);
      int mx = sum[0];
      for(idx = 0; idx < len; idx++)
	 if(sum[idx] > mx)
	     mx =sum[idx];
	 return mx;
}
int main()
{
      int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
      int ans = maximum_subarray_sum(arr, len);
      printf("%d",ans);
      return 0;
}

#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "efgfe";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

#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>
#include<string.h>
int get_min(int a, int b)
{
     if(a < b)
         return a;
     return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
              min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
              if(s1[i - 1] == s2[j - 1])
              {
                  if(arr[i-1][j-1] < min)
                     min = arr[i-1][j-1];
              }
              else
              {
                  if(arr[i-1][j-1] + 1 < min)
                      min = arr[i-1][j-1] + 1;
              }
              arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "dcba";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}