Number of Coins

Given a value V and array coins[] of size M, the task is to make the change for V cents, given that you have an infinite supply of each of coins{coins1, coins2, …, coinsm} valued coins. Find the minimum number of coins to make the change. If not possible to make change then return -1.

• Time : O(nv)
• Space : O(v)

class Solution {
public:
    int minCoins(int coins[], int n, int V) {
        vector<int> dp(V + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 0; i < n; i++) {
            for(int j = coins[i]; j <= V; j++) {
                if(dp[j-coins[i]] == INT_MAX) continue;
                dp[j] = min(dp[j], dp[j-coins[i]] + 1);
            }
        }
        
        return dp[V] == INT_MAX ? -1 : dp[V];
    }
};