leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0322.cpp (453B)

      1 // DP solution
      2 class Solution {
      3   public:
      4     int coinChange(vector<int> &coins, int amount) {
      5         vector<int> dp(amount + 1, INT_MAX);
      6         dp[0] = 0;
      7 
      8         for (int i = 0; i < amount; i++) {
      9             if (dp[i] == INT_MAX) continue;
     10             for (int coin : coins)
     11                 if ((long long)coin + i <= amount) dp[coin + i] = min(dp[coin + i], dp[i] + 1);
     12         }
     13         return dp[amount] != INT_MAX ? dp[amount] : -1;
     14     }
     15 };