c++ dp(46ms) solution and BFS(26ms) solution


  • 0
    J

    dp solution:

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            int len=coins.size();
            vector<int> dp(amount+1, INT_MAX);
            dp[0]=0;
            for(int i=1; i<=amount; i++)
            {
                for(int j=0; j<len; j++)
                {
                    int val=i-coins[j];
                    if(val>=0 && dp[val] != INT_MAX)
                        dp[i]=min(dp[i], 1+dp[val]);
                }
            }
            return dp[amount]==INT_MAX?-1:dp[amount];
        }
    };
    

    BFS solution. visited vector to record the amount being visited is the key to save the time

     int coinChange(vector<int>& coins, int amount) {
            int len=coins.size();
            if(amount<0)
                return -1;
            if(amount==0)
                return 0;
            vector<int> visited(amount+1, false);
            int level=0;
            int ans=INT_MAX;
            queue<int> Q;
            Q.push(amount);
            visited[amount]=true;
            while(!Q.empty())
            {
                int sz=Q.size();
                ++level;
                for(int i=0; i<sz; i++)
                {
                    
                    int temp=Q.front();
                    Q.pop();
                    for(int i=0; i<len; i++)
                    {
                        int val=temp-coins[i];
                        if(val==0)
                        {
                            ans=min(ans, level);
                        }
                        if(val>0 && visited[val]==false)
                        {
                            visited[val]=true;
                            Q.push(val);
                        }
                    }
                }
            }
            return ans==INT_MAX?-1:ans;
        }
    

Log in to reply
 

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