Min Number Of Coins For Change

• Time : O(nd)
• Space : O(n)

c++

#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();
}