8 ms,15 lines concise DFS solution[c++]


  • 2
    Z
    int coinChange(vector<int>& coins, int amount) {
            sort(coins.begin(),coins.end());
            return coinChange(coins,amount,coins.size()-1,0,*(new int(INT_MAX)));
        }
        int coinChange(vector<int>&coins,int amount,int idx,int cur,int &cand){
            if(!amount)return cand=cur;
            if(idx<0)return -1;
            int flag=0,n=amount/coins[idx];
            if(n+cur>=cand)return -1;
            for(int i=n;i>=0;i--){
                if(coinChange(coins,amount-i*coins[idx],idx-1,cur+i,cand)!=-1) flag=1;
            }
            if(flag) return cand;
            return -1;
        }

  • 0
    Q

    My code uses the same concept as yours, except I don't return minimum directly. Why it takes 402ms? Could you please take a look for me? Thanks.

    class Solution {
    public:
    
        int coinChange(vector<int>& coins, int amount) {
            int Min = amount; //assume one is the smallest coin
            //here is an example of using big coins not always to be the best
            //  coin:{9, 8, 1},  target 32   
            int count = 0;
            int maxCoinIndex = 0;
            unordered_map<int, int> table;
            sort(coins.begin(), coins.end(), greater<int>());
            if( -1 != coinChange(coins, maxCoinIndex, amount, count, Min))
               return Min;
             return -1;
        }
        //if use table, every place that returns must record
        int coinChange(vector<int>& coins, int maxCoinIndex, int amount, int count, int& Min)
        {
            
            int maxCoin = coins[maxCoinIndex];
            int temp = amount/maxCoin;
            if(temp+count > Min) {
                return -1;
            }
            if(amount%maxCoin == 0) 
            {
                Min = min(Min, temp+count);
                return temp;
            } else// not dividable
            {
                if(maxCoinIndex == coins.size()-1) {
                  return -1;
                }
                int localMin = amount+count;
                bool noWay = true;
                int deduct = 0;
                for(int i=0; deduct < amount; ++i, deduct += maxCoin)
                {
                    if (count+i > Min) {
                    return -1;}
                    int temp = coinChange(coins, maxCoinIndex+1, amount - deduct, count+i,  Min);
                    if(temp == -1) 
                    {
                        continue;
                    } else
                    {
                       localMin = min(localMin, i + temp);
                       noWay = false;  
                    }
                }
                if(noWay){
                    return -1;
                }
                Min = min(Min, localMin+count);
                return localMin;
            }
        }
    };

  • 0
    Z
    This post is deleted!

  • 0
    Z

    @quesder I have viewed your code and we have almost the same idea.But I think your code lack some integration,which may cause your algorithm to do too much unnecessary computing for each iteration.You can just simplify your code.


Log in to reply
 

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