C++ DP solution


  • 0
    S
    int coinChange(vector<int>& coins, int amount) {
            const int MAX_INT = 0x7ffffffe;
            int cnt[amount+1];
            for(int i = 1; i <= amount; i++) cnt[i] = MAX_INT;
            cnt[0] = 0;
            for(int i = 0; i <= amount; i++){
                 for(int j = 0; j < coins.size(); j++){
                     if(coins[j] + i <= amount)
                         cnt[coins[j] + i] = min(cnt[coins[j] + i],cnt[i]+1);
                 }
            }
            return cnt[amount] == MAX_INT? -1: cnt[amount];
     }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.