Answers for "coin change problem maximum number of ways"

coin change problem minimum number of coins dynamic programming

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);
        }
    }
}

coin change problem maximum number of ways

#include <iostream>

using namespace std;
int solve(int n,int sum,int coin[])
{
    int dp[n+1][sum+1];
    for(int i=0;i<=sum;i++)
    {
        dp[0][i]=0;
    }
     for(int i=0;i<=n;i++)
    {
        dp[i][0]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=sum;j++)
        {
            if(coin[i-1]<=j)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-coin[i-1]];
            }
            else
            {
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    return dp[n][sum];
}
int main()
{
    int n;
    cin>>n;
    int coin[n];
    for(int i=0;i<n;i++)
    {
        cin>>coin[i];
    }
    int sum;
    cin>>sum;
    cout<<solve(n,sum,coin);
    return 0;
}