number of coins

// time O(V*M), space O(V + 1)
// Approach: Basic top-down DP over recursion
class Solution {

	public:
	
	int makeChange(int coins[], int M, int V, vector<int>& dp) {
	    if(V == 0) {
	        return 0;
	    }
	    else if(dp[V] != -2) {
	        return dp[V];
	    }
	    else {
	        int minCoin = INT_MAX;
	        for(int i = 0; i < M; ++i) {
	            if(V - coins[i] >= 0) {
	                int smallChange = makeChange(coins, M, V - coins[i], dp);
	                if(smallChange != -1) {
	                    minCoin = min(minCoin, 1 + smallChange);
	                }
	            }
	        }
	        dp[V] = minCoin == INT_MAX ? -1 : minCoin;
	        return dp[V];
	    }
	}
	
	int minCoins(int coins[], int M, int V) {
	    vector<int> dp(V + 1, -2);
	    int minCoin = makeChange(coins, M, V, dp);
	    return minCoin;
	}
	  
};