My DP (100ms) & BFS (64ms) C++ solutions


  • 0
    D

    First, BFS solution. In this solution, nodes[cur..curEnd) save all the possible amounts that can be combined with steps coins. For each while loop, we try to extend nodes[cur..curEnd) by adding a new coin to nodes[cur..curEnd). To avoid revisiting nodes that are visited before, an array visited is used to indicate whether the amount i is reached/visited before.

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            if(amount < 0) return -1;
            if(amount ==0) return 0;
            bool visited[amount]; // flag to indicate whether the amount i is visited before
            fill_n(visited, amount, false);
            int nodes[amount], cur=0, curEnd=1, j, newEnd = 1,newN, steps=0;
            nodes[0] = 0; //starting from the amount of 0
            while(cur<curEnd) 
            { // if there are still some amounts that are smaller than "amount" that we can extend by adding a coin
                for(++steps;cur<curEnd; ++cur)
                { // extend each nodes at the current level
                    for(j=0; j<coins.size();++j)
                    { // extending by adding a new coin
                        newN = nodes[cur] + coins[j];
                        if(newN== amount) // if the new amount is equal to "amount", return steps
                            return steps;
                        else if(newN< amount)
                        { 
                            if(!visited[newN]) 
                            { // if the new amount is not visited before, add to the queue for next while loop
                                nodes[newEnd++] = newN;
                                visited[newN] = true;
                            }
                        }
                    }
                }
                curEnd = newEnd;
            }
            return -1;
        }
    

    };

    Then DP algorithm,
    Using an array steps to save the minimum coins that can combine together to get "amount", steps[i]=-1 means i can not be reached.

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            if(amount < 0) return -1;
            if(amount ==0) return 0;
            int steps[amount+1], res = -1, i, j;
            fill_n(steps, amount+1, -1);
            for(i=0,steps[i]=0; i<amount;++i)
            {
                if(steps[i]<0) continue; // if i is not reachable, then skip it.
                for(j=0; j<coins.size();++j)
                    if(i+coins[j]<= amount && (steps[i+coins[j]]<0 || steps[i+coins[j]] > steps[i]+1) ) 
                        steps[i+coins[j]] = steps[i]+1; // if the current combination needs less coins, then update it.
            }
            return steps[amount];
        }
    };

Log in to reply
 

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