Min Number Of Coins For Change
- Time : O(nd)
- Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <vector>
using namespace std;
int minNumberOfCoinsForChange(int n, vector<int> denoms) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for(auto& denom : denoms) {
for(int i = denom; i <= n; i++) {
if(dp[i - denom] == INT_MAX) continue;
dp[i] = min(dp[i], dp[i-denom] + 1);
}
}
return dp.back() == INT_MAX ? -1 : dp.back();
}
|
