7 lines DP Java solution. 28ms. O(amount*coins.length) time and O(amount) space complexity.


  • 1
    O
    
        public int coinChange(int[] coins, int amount) {
        	int[] memo = new int[amount+1];
        	Arrays.fill(memo, amount+1);
        	memo[0] = 0;
        	for(int i = 1; i <= amount; i++) 
        		for(int j = 0; j < coins.length; j++) 
        			if(coins[j] <= i) memo[i] = Math.min(memo[i], memo[i-coins[j]] + 1);
        	return memo[amount] > amount ? -1 : memo[amount];
        }
    

Log in to reply
 

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