number of coins (iterative)
unknown
c_cpp
a year ago
561 B
7
Indexable
Never
// 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]; } };