Java DP simple accepted solution


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

Log in to reply
 

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