number of coins
unknown
c_cpp
a year ago
852 B
1
Indexable
Never
// 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; } };