16. Min. No . of Coins

GFG problem link --> https://practice.geeksforgeeks.org/problems/number-of-coins1824/1

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution{

	public:
	int minCoins(int coins[], int n, int v) 
	{ 
	    // Your code goes here
	    
	    int t[n+1][v+1];
	  
	  for(int i=0;i<n+1;i++){
	      for(int j=0;j<v+1;j++){
	          
	          if(j==0){
	              t[i][j]=0;
	          }
	          
	          if(i==0){
	               
	           //here we will need imfinite coins to sum up to any vlaue with givn condn. that coins 
	           //array is empty 
	              
	            t[i][j]=INT_MAX -1;     
	          }
	          
	          
	          
	          
	      }
	  }
	    
	   //here we need to initilaise the second row too
	   
	   
	   for(int j=0;j<v+1;j++)
	   {
	       
	       
	       if( j % coins[0]==0)
	       {
	           t[1][j]= j/coins[0];
	       }
	       else{
	           
	           //if value is not divisible by coins's value (arr[0]) then the required value cant be 
	           //obtained by that paritcular coin . Hence no. of min .  coin will be infinte  
	           t[1][j]=INT_MAX-1;
	       }
	       
	   }
	    
	    
	    for(int i=2;i<n+1;i++)
	    {
	        for(int j=1;j<v+1;j++)
	        {
	            
	            
	            if(coins[i-1]<= j){
	                t[i][j]= min( 1+  t[i][j-coins[i-1]] , t[i-1][j] );
	            }
	            
	            else{
	                t[i][j]=t[i-1][j];
	                
	            }
	            
	        }
	    }
	    
	    
	    if(t[n][v]==INT_MAX-1){
	        return -1;
	    }
	    
	    return t[n][v];
	    
	    
	} 
	  
};

//{ Driver Code Starts.
int main() 
{
   
   
   	int t;
    cin >> t;
    while (t--)
    {
        int v, m;
        cin >> v >> m;

        int coins[m];
        for(int i = 0; i < m; i++)
        	cin >> coins[i];

      
	    Solution ob;
	    cout << ob.minCoins(coins, m, v) << "\n";
	     
    }
    return 0;
}

// } Driver Code Ends