leetcode

0 // DP solution

1 class Solution {

2 public:

3 int coinChange(vector<int> &coins, int amount) {

4 vector<int> dp(amount + 1, INT_MAX);

5 dp[0] = 0;

6

7 for (int i = 0; i < amount; i++) {

8 if (dp[i] == INT_MAX) continue;

9 for (int coin : coins)

10 if ((long long)coin + i <= amount) dp[coin + i] = min(dp[coin + i], dp[i] + 1);

11 }

12 return dp[amount] != INT_MAX ? dp[amount] : -1;

13 }

14 };