Dynamic Programming in Data Structures MCQ question and answer with solution

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      strrev(str2);
      int arr[len + 1][len + 1];
      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(str1[i-1] == str2[j - 1])
                  arr[i][j] = 1 + arr[i - 1][j - 1];
              else
                  arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return arr[len][len];
}
int main()
{
      char str1[] = "abdgkagdjbccbba";
      int ans = lps(str1);
      printf("%d",ans);
      return 0;
}

#include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
      int arr[n][n];
      int i,k,row,col,len;
      for(i=1;i<n;i++)
          arr[i][i] = 0;
      for(len = 2; len < n; len++)
      {
           for(row = 1; row <= n - len + 1; row++)
           {
               col = row + len - 1;
               arr[row][col] = INT_MAX;
               for(k = row; k <= col - 1; k++)
               {
                    int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
                    if(tmp < arr[row][col])
                    arr[row][col] = tmp;
               }
           }
      }
      return arr[1][n - 1];
}
int main()
{
     int mat[6] = {20,5,30,10,40};
     int ans = mat_chain_multiplication(mat,5);
     printf("%d",ans);
     return 0;
}

#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(max_price, prices[i] + rod_cut(prices,len - i - 1)); 
      return max_price;
}
int main()
{
      int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
      int ans = rod_cut(prices, len_of_rod);
      printf("%d",ans);
      return 0;
}

#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(max_price, prices[i] + rod_cut(prices,len - i - 1)); 
      return max_price;
}
int main()
{
      int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
      int ans = rod_cut(prices, len_of_rod);
      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[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
           for(j = 1; j <= len2; j++)
           {
                if(str1[i-1] == str2[j - 1])
                    arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                    arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
           }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}