java DP solution


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

Log in to reply
 

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