Time Cost

15min11s

Implementation

DP

Code

• My Solution

  class Solution {
  public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(), coins.end());
        vector<int> fewestnum(amount + 1, -1);
        fewestnum[0] = 0;
        for (int coin: coins) {
            if (coin <= amount) {
                fewestnum[coin] = 1;
            }
        }
  
        for (int i=1; i<=amount; i++) {
            for (int coin: coins) {
                if (i - coin >= 0 && fewestnum[i-coin] != -1) {
                    if (fewestnum[i] == -1) {
                        fewestnum[i] = fewestnum[i-coin]+1;
                    }else{
                        fewestnum[i] = min(fewestnum[i-coin]+1, fewestnum[i]);
                    }
                }
            }
        }
  
        return fewestnum[amount];
    }
  };