Share my cpp solution, O(m*n)


  • 0
    int coinChange(vector<int>& coins, int amount) 
    {
        vector<long long int> coin_size(amount + 1, INT_MAX);
        int total = 0;
        
        coin_size[total] = 0;
        for (total = 1; total <= amount; total++)
        {
            for (int j = 0; j < coins.size(); j++)
            {
                if (coins[j] <= total)
                {
                    coin_size[total] = min(coin_size[total], coin_size[total - coins[j]] + 1);
                }
            }
        }
        
        return coin_size[amount] < INT_MAX ? coin_size[amount] : -1;
    }
    

    case overflow.


Log in to reply
 

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