Evolve from brute force to optimal, a review of all solutions


  • 0

    This is similar to word break and perfect square

    1. O(n^s) brute force
        int coinChange(vector<int>& coins, int amount) {
            if(amount==0) return 0;
            if(amount<0) return -1;
            int cc = -1;
            for(int i=0;i<coins.size();i++) {
                int coin = coinChange(coins,amount-coins[i]);
                if(coin>=0) cc = cc < 0 ? coin : min(cc,coin);
            }
            return cc <0 ? -1 : cc+1;
        }
    
    1. O(ns) pseudo polynomial dfs with Memoization
        int coinChange(vector<int>& coins, int amount) {
            unordered_map<int,int> mem;
            return coinChange(amount,mem,coins);    
        }
        int coinChange(int amount, unordered_map<int,int>& mem, vector<int>& coins) {
            if(amount==0) return 0;
            if(amount<0) return -1;
            auto it = mem.find(amount);
            if(it != mem.end()) return it->second;
            int cc = amount+1;
            for(int i=0;i<coins.size();i++) {
                int coin = coinChange(amount-coins[i],mem,coins);
                if(coin>=0) cc = min(cc,coin);
            }
            return mem[amount] = cc > amount ? -1 : cc+1;
        }
    
    1. O(ns) pseudo polynomial dp
        int coinChange(vector<int>& coins, int amount) {
            vector<int> dp(amount+1, amount+1);
            dp[0]=0;
            for(int i=0;i<=amount;i++)
                for(int c:coins) 
                    if(c<=i) dp[i] = min(dp[i],dp[i-c]+1);
            return dp[amount]>amount? -1 : dp[amount];    
        }
    
    1. O(ns) traditional bfs with q and visited flag
        int coinChange(vector<int>& coins, int amount) {
            unordered_set<int> vstd;
            queue<int> q({0});
            int cc=0;
            while(!q.empty()) {
                int n = q.size();
                for(int i=0;i<n;i++) {
                    int a = q.front();
                    q.pop();
                    if(a==amount) return cc;
                    if(a>amount || vstd.count(a)) continue;
                    vstd.insert(a);
                    for(int c:coins) q.push(a+c);
                }
                cc++;
            }
            return -1;
        }
    
    1. bfs that caches two levels only.
        int coinChange(vector<int>& coins, int amount) {
            unordered_set<int> cur({0}), nxt, *p_cur=&cur,*p_nxt=&nxt;
            int cc=0;
            while(!p_cur->empty()) {
                for(int a:*p_cur) {
                    if(a==amount) return cc;
                    if(a>amount) continue;
                    for(int c:coins) p_nxt->insert(a+c);
                }
                swap(p_cur,p_nxt);
                p_nxt->clear();
                cc++;
            }
            return -1;
        }
    
    1. Two end bfs
        int coinChange(vector<int>& coins, int amount) {
            unordered_set<int> begin({0}), end({amount}), nxt, vstd, *p_sm=&begin, *p_lg = &end, *p_nxt=&nxt;
            int cc=0;
            bool isBegin = 1;
            while(!p_sm->empty() && !p_lg->empty()) {
                if(p_sm->size()>p_lg->size()) {
                    swap(p_sm,p_lg);
                    isBegin = !isBegin;
                }
                for(int a:*p_sm) {
                    if(p_lg->count(a)) return cc;
                    if(a>amount) continue;
                    for(int c:coins) p_nxt->insert(isBegin?a+c:a-c);
                }
                swap(p_sm,p_nxt);
                p_nxt->clear();
                cc++;
            }
            return -1;
        }
    

    I think dfs with memorization and bfs are better because they don't visit invalid states while test cases show that dp is the fastest.


Log in to reply
 

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