coin change problem minimum number of coins dynamic programming

// A Dynamic Programming based C++ program to find minimum of coins 
// to make a given change V 
#include<bits/stdc++.h> 
using namespace std; 
  
// m is size of coins array (number of different coins) 
int minCoins(int coins[], int m, int V) 
{ 
    // table[i] will be storing the minimum number of coins 
    // required for i value.  So table[V] will have result 
    int table[V+1]; 
  
    // Base case (If given value V is 0) 
    table[0] = 0; 
  
    // Initialize all table values as Infinite 
    for (int i=1; i<=V; i++) 
        table[i] = INT_MAX; 
  
    // Compute minimum coins required for all 
    // values from 1 to V 
    for (int i=1; i<=V; i++) 
    { 
        // Go through all coins smaller than i 
        for (int j=0; j<m; j++) 
          if (coins[j] <= i) 
          { 
              int sub_res = table[i-coins[j]]; 
              if (sub_res != INT_MAX && sub_res + 1 < table[i]) 
                  table[i] = sub_res + 1; 
          } 
    } 
    return table[V]; 
} 
  
// Driver program to test above function 
int main() 
{ 
    int coins[] =  {9, 6, 5, 1}; 
    int m = sizeof(coins)/sizeof(coins[0]); 
    int V = 11; 
    cout << "Minimum coins required is "
         << minCoins(coins, m, V); 
    return 0; 
} 

# A Dynamic Programming based Python3 program to  
# find minimum of coins to make a given change V 
import sys  
  
# m is size of coins array (number of  
# different coins) 
def minCoins(coins, m, V): 
      
    # table[i] will be storing the minimum  
    # number of coins required for i value.  
    # So table[V] will have result 
    table = [0 for i in range(V + 1)] 
  
    # Base case (If given value V is 0) 
    table[0] = 0
  
    # Initialize all table values as Infinite 
    for i in range(1, V + 1): 
        table[i] = sys.maxsize 
  
    # Compute minimum coins required  
    # for all values from 1 to V 
    for i in range(1, V + 1): 
          
        # Go through all coins smaller than i 
        for j in range(m): 
            if (coins[j] <= i): 
                sub_res = table[i - coins[j]] 
                if (sub_res != sys.maxsize and 
                    sub_res + 1 < table[i]): 
                    table[i] = sub_res + 1
    return table[V] 
  
# Driver Code 
if __name__ == "__main__": 
  
    coins = [9, 6, 5, 1] 
    m = len(coins) 
    V = 11
    print("Minimum coins required is ",  
                 minCoins(coins, m, V)) 
  
# This code is contributed by ita_c 

class Main
{
    // Function to find the minimum number of coins required
    // to get total of N from set S
    public static int findMinCoins(int[] S, int N)
    {
        // T[i] stores minimum number of coins needed to get total of i
        int[] T = new int[N + 1];
 
        for (int i = 1; i <= N; i++)
        {
            // initialize minimum number of coins needed to infinity
            T[i] = Integer.MAX_VALUE;
            int res = Integer.MAX_VALUE;
 
            // do for each coin
            for (int c: S)
            {
                // check if index doesn't become negative by including
                // current coin c
                if (i - c >= 0) {
                    res = T[i - c];
                }
 
                // if total can be reached by including current coin c,
                // update minimum number of coins needed T[i]
                if (res != Integer.MAX_VALUE) {
                    T[i] = Integer.min(T[i], res + 1);
                }
            }
        }
 
        // T[N] stores the minimum number of coins needed to get total of N
        return T[N];
    }
 
    public static void main(String[] args)
    {
        // n coins of given denominations
        int[] S = { 1, 2, 3, 4 };
 
        // Total Change required
        int N = 15;
 
        int coins = findMinCoins(S, N);
        if (coins != Integer.MAX_VALUE) {
            System.out.print("Minimum number of coins required to get desired change is "
                + coins);
        }
    }
}