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