i annot find out why it is wrong,please tell me ,thanks


  • 0
    X
    int coinChange(vector<int>& coins, int amount) 
    {
        sort(coins.begin(),coins.end());
        vector<int> vec(amount+1);
        vec[0]=0;
        for(int i=1;i<=amount;i++)
        {
            vec[i]=-1;
            for(int j=coins.size()-1;j>=0;j--)
            {
                if(i>=coins[j]&&vec[i-coins[j]]!=-1)
                {
                    vec[i]=vec[i-coins[j]]+1;
                    break;
                }
            }
        }
        return vec[amount];
    }

  • 1
    S

    The solution should compute the fewest number of coins ,so you should use

    vec[i]= min(vec[i],vec[i-coins[j]]+1); 
    

    instead of

    vec[i]=vec[i-coins[j]]+1;
    

    Here is the solution the OJ accepted.

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

  • 0
    X

    @solosseason thank you very much


Log in to reply
 

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