Maximize The Cut Segments-dynamic programming

this sum is taken from geeksforgeeks

if you want to solve you can go to this link

https://practice.geeksforgeeks.org/problems/cutted-segments/0

Given an integer N denoting the Length of a line segment. you need to cut the line segment in such a way that the cut length of a line segment each time is integer either x , y or z. and after performing all cutting operation the total number of cutted segments must be maximum. 

N=4

x,y,z=2 1 1

In first test case, total length is 4, and cut lengths are 2, 1 and 1.  We can make maximum 4 segments each of length 1. 

so output=>4

N=5

x=5 ,y=3,z=2

 we can make two segments of lengths 3 and 2.

output=>2

lets use dynamic programming to solve this question:

c++ implementation:

t is the no.of test cases:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void mtcs(int a[],int length)
{    
      int dp[3][length+1];     
    int j=0;
       for(int i=0;i<3;i++)
       {
           for(j=0;j<=length;j++)
           {  if(j==0)
              dp[i][j]=0;
              
              else if(i==0)
              {   if(j%a[i]==0)
                  dp[i][j]=j/a[i];
                  else
                  dp[i][j]=0;
              }
        
        
              else{
                  if(a[i]>j) 
                  dp[i][j]=dp[i-1][j];
                  
                  else
                  {
                       if(dp[i-1][j]==0 && dp[i][j-a[i]]==0 && j-a[i]!=0)
                         dp[i][j]=0;
                         
                       else
                         dp[i][j]=max(dp[i-1][j],dp[i][j-a[i]]+1);
                  }
                  
                  }
             
           }
       }
       
cout<<dp[2][j-1];
}

int main() {
int t; cin>>t;
while(t--)
{  int length;   cin>>length;
    

   
int a[3];
cin>>a[0]>>a[1]>>a[2];
sort(a,a+3);

mtcs(a,length);
  cout<<endl;  
}
 return 0;
}