Share my clean and easy Java solution with explanation


  • 1
    C

    The idea is using an array to store the number of coins for making up the amount. We can treat the index of the array as the target amount.

    If the coin's denomination equals to the index, we can simply set dp[index] = 1 since we only need one coin.

    Otherwise if coin's denomination is less than the index but dp[index - coin's denomination] isn't 0 (which means we can already make up the amount of "index - coin's denomination"), we can still make up the amount of 'index' by adding one more coin.

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

Log in to reply
 

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