Java Solution using Dynamic Programming


  • 0
    E
    public class Solution {
        public int coinChange(int[] coins, int amount) {
        	Arrays.sort(coins);
            int dp[][]=new int[coins.length][amount+1];
            int big=Integer.MAX_VALUE-1;
            for(int i=1;i<=amount;i++){
            	dp[0][i]=i%coins[0]==0?i/coins[0]:big;
            }
            for(int i=1;i<coins.length;i++){
                for(int j=1;j<=amount;j++){
                    if(j<coins[i]){
                        dp[i][j]=dp[i-1][j];
                    }
                    else{
                        if(dp[i][j-coins[i]]==big && dp[i-1][j]==big){
                            dp[i][j]=big;
                        }
                        else{
                            dp[i][j]=Math.min(dp[i][j-coins[i]]+1,dp[i-1][j]);
                        }
                    }
                }
            }
            return dp[coins.length-1][amount]==big?-1:dp[coins.length-1][amount];
        }
    }
    

Log in to reply
 

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