[LeetCode] 322 Coin Change

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int coinChange(vector<int>& coins, int amount) { constexpr int MAX = 10001; int dp[MAX]; for (int i = 0; i < MAX; i++) dp[i] = MAX; dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int &coin : coins) { if (i >= coin) dp[i] = min(dp[i], dp[i - coin] + 1); } } if (dp[amount] == MAX) return -1; return dp[amount]; } };