1int coinChange(int* coins, int n, int amount) {
2 int dp[amount + 1];
3 for (int i = 0; i <= amount; i++) dp[i] = INT_MAX;
4 dp[0] = 0;
5 for (int a = 1; a <= amount; a++) {
6 for (int k = 0; k < n; k++) {
7 if (coins[k] <= a && dp[a - coins[k]] != INT_MAX)
8 if (dp[a - coins[k]] + 1 < dp[a])
9 dp[a] = dp[a - coins[k]] + 1;
10 }
11 }
12 return dp[amount] == INT_MAX ? -1 : dp[amount];
13}
