| 4 | class Solution { |
| 5 | public: |
| 6 | int coinChange(vector<int>& coins, int amount) { |
| 7 | const int INF = 1e9; |
| 8 | vector<int> dp(amount + 1, INF); |
| 9 | dp[0] = 0; |
| 10 | |
| 11 | for (int coin : coins) { |
| 12 | for (int i = coin; i <= amount; i++) { |
| 13 | dp[i] = min(dp[i], dp[i - coin] + 1); |
| 14 | } |
| 15 | } |
| 16 | return dp[amount] == INF ? -1 : dp[amount]; |
| 17 | } |
| 18 | }; |
| 19 | |
| 20 | int main() { |