Dynamic Programming in Data Structures MCQ question and answer with solution

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)
                      ____________;
              }
              else
              {
                  if(arr[i-1][j-1] + 1 < min)
                      min = arr[i-1][j-1] + 1;
              }
              arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}

#include<stdio.h>
int get_min(int a, int b)
{
      if(a<b)
        return a;
      return b;
}
int minimum_time_required(int reach[][4],int spent[][5], 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[][4] = {{16, 10, 5, 12},
                           {12, 4, 17, 8}};
     int time_spent[][5] = {{13, 5, 20, 19, 9},
                        {15, 10, 12, 16, 13}};
     int entry_time[2] = {12, 9};
     int exit_time[2] = {10, 13};
     int num_of_stations = 5;
     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 find_max(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
     int ans[n + 1][W + 1];
     int itm,w;
     for(itm = 0; itm <= n; itm++)
         ans[itm][0] = 0;
     for(w = 0;w <= W; w++)
        ans[0][w] = 0;
     for(itm = 1; itm <= n; itm++)
     {
          for(w = 1; w <= W; w++)
          {
               if(wt[itm - 1] <= w)
                ans[itm][w] = find_max(ans[itm - 1][w - wt[itm - 1]]+val[itm - 1], ans[itm - 1][w]);
               else
                ans[itm][w] = ans[itm - 1][w];
          }
     }
     return ans[n][W];
}
int main()
{
     int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
     int ans = knapsack(W, w, v, 3);
     printf("%d",ans);
     return 0;
}

#include<stdio.h>
#include<limits.h>
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int kadane_algo(int *arr, int len)
{
      int ans, sum, idx;
      ans =0;
      sum =0;
      for(idx =0; idx < len; idx++)
      {
          sum = max_num(0,sum + arr[idx]);
          ans = max_num(sum,ans);
      }
      return ans;
}
int max_sum_rectangle(int arr[][5],int row,int col)
{
      int left, right, tmp[row], mx_sm = INT_MIN, idx, val=0;
      for(left = 0; left < col; left++)
      {
           for(right = left; right < col; right++)
           {
               if(right == left)
               {
                   for(idx = 0; idx < row; idx++)
                      tmp[idx] = arr[idx][right];
               }
               else
               {
                   for(idx = 0; idx < row; idx++)
                      tmp[idx] += arr[idx][right];
               }
               val = kadane_algo(tmp,row);
               if(val > mx_sm)
               mx_sm = val;
           }
      }
      return mx_sm;
}
int main()
{
      int arr[4][5] ={{ 7,  1, -3, -6, -15},
                    { 10,  -6,  3,  -4,  11},
                    { -2, -3, -1,  2, -5},
                    { 3,  0,  1,  0,  3}};
      int row = 4, col = 5;
      int ans = max_sum_rectangle(arr,row,col);
      printf("%d",ans);
      return 0;
}

#include<stdio.h>
int main()
{
      int coins[10]={1,3,4},lookup[100];
      int i,j,tmp,num_coins = 3,sum=14;
      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;
}