4ms C++ solution (beats 99.65%)


  • 1
    P
    #define MIN_COINS(x, y) (((x) + (y) - 1)/(y))                                   
    class Solution {                                                                
     // leetcode.com stats : 4ms, beats 99.65%                                      
    public:                                                                         
        int coinChange(vector<int>& coins, int amount) {                                
            sort(coins.begin(), coins.end(), std::greater<int>());                          
            known_min_ = INT_MAX;                                                           
            change(amount, 0, coins, 0);                                                    
            return (known_min_ == INT_MAX) ? -1 : known_min_;                               
        }                                                                               
    private:                                                                        
        void change(int amount, int lbound, const vector<int> &coins, int cstart) {     
            int n = amount / coins[cstart];                                         
            for (int i = n ; i >= 0; i--) {                                         
                int rem = amount - (i*coins[cstart]);                                       
                int cur_coins = lbound + i;                                         
                if ((rem > 0) && ((cstart+1) < coins.size())                        
                     && ((cur_coins + MIN_COINS(rem, coins[cstart+1])) < known_min_)) {
                    change(rem, lbound+i, coins, cstart+1);                           
                } else if ((rem == 0) && (cur_coins < known_min_)) {                
                    known_min_ = cur_coins;                                         
                } else {                                                            
                   break;                                                           
                }                                                                   
            }                                                                       
            return;                                                                 
        }                                                                           
                                                                                    
        int known_min_;                                                             
    };

Log in to reply
 

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