Concise DP solution


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

Log in to reply
 

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