112ms C++ solution


  • 2
    D
    class Solution {
    public:
    	int coinChange(vector<int>& coins, int amount)
    	{
    		if (coins.empty()) return 0;
    		vector<int> DP(amount + 1, INT_MAX-1);
    		DP[0] = 0;
    		for (int i = 0; i < coins.size(); i++)
    		{
    			for (int j = coins[i]; j <= amount; j++)
    			{
    				DP[j] = min(DP[j], DP[j-coins[i]] + 1);
    			}
    		}
    		if (DP[amount] < INT_MAX-1) return DP[amount];
    		else return -1;
    	}
    };

  • 0
    Y

    Clean and tidy and readable.

    A few people lists some edge cases which can't help too much performance in general.


Log in to reply
 

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