number of coins (iterative)

// AMAN JAIN MCA 1st YEAR 2nd SEM

// time O(V*M) space(V)
// Approach: Bottom up dynamic programming
class Solution {
public:
	
	int minCoins(int coins[], int M, int V) { 
	    vector<int> dp(V + 1, -1);
	    dp[0] = 0;
	    for(int i = 1; i <= V; ++i) {
	        int minCoin = INT_MAX;
	        for(int j = 0; j < M; ++j) {
	            if(i - coins[j] >= 0 && dp[i - coins[j]] != -1) {
	                minCoin = min(minCoin, 1 + dp[i - coins[j]]);
	            }
	        }
	        dp[i] = minCoin == INT_MAX ? -1 : minCoin;
	    }
	    return dp[V];
	}
};