Simplest Java solution. Beat 89%


  • 4

    The problem is typical Knapsack problem.

    https://en.wikipedia.org/wiki/Knapsack_problem

    The idea is, each coin can be used infinitely. So the inner loop of dp is ascending. If one coin can only be used once, the inner loop should be descending.

    public class Solution {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            
            for (int coin : coins) {
                for (int j = coin; j <= amount; j++) {
                    if (dp[j - coin] != Integer.MAX_VALUE) {
                        dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                    }
                }
            }
            
            return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
        }
    }
    

  • 0
    S

    I can't understand the relationship between this question and Knapsack_problem, can you give more details about this?
    This is what I get from your code:
    For each iteration, the dp[] result shows that the minimum number of coins combined for each amount. Let's take 11 and [5,2,1] for example. After the first iteration of coin 5, we can know whether the amount can be expressed by coin 5 and what is the minimum number. The second iteration uses the previous result of coin 5 to determine which amounts can expressed by the combination of 5 and 3 and what is the minimum amount needed by Math.min(dp[i], dp[i - coin] + 1).
    And so on..


Log in to reply
 

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