DP AC JAVA Solution 18ms Beating 95%


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

  • 0
    D

    can you please explain the logic.


  • 0
    J

    I don't think your code actually works for all input, although it passes the test. Previous coin cannot see results of coin afterwards, you may get different answer if you change the order of coins in the coin array.


  • 0
    T

    @FightForGoogle It will work even if the order of the coins change because the results are based on the previous dp result. Let's take 11 and [5,2,1] for example. After the first iteration which uses the coin 5, dp result is [0,m,m,m,m,1,m,m,m,m,2,m]. The second iteration with coin 3, dp result is [0,m,1,m, 2,1,3,2,4,2,m ]. The last one is [0, 1, 1, 2, 2, 1, 2, 2, 3, 2, 3].

    In sum, for each iteration, the dp result represents that each amount can be expressed by all the coins used before.


  • 2
    T

    @daredevil89 Actually, 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..


  • 0
    J

    @tjweichang You are absolutely right, the order of coins chosen doesn't matter the result. Thanks.


  • 0
    F

    what about coins = [1] and amount = Integer.MAX_VALUE?


  • 3
    G

    This solution is mysterious at first, but I like thinking of it as finding the shortest coin-path to all amounts up to and including the given amount.

    Consider OP's algorithm's behavior on the given array {5, 2, 1}, for the amount of 11:

    Coin: 5
       amount: 5
          Current route: 1
          Previous route: 2147483647
          Saving best route, dp[5] = 1
       amount: 6
       amount: 7
       amount: 8
       amount: 9
       amount: 10
          Current route: 2
          Previous route: 2147483647
          Saving best route, dp[10] = 2
       amount: 11
    
    Coin: 2
       amount: 2
          Current route: 1
          Previous route: 2147483647
          Saving best route, dp[2] = 1
       amount: 3
       amount: 4
          Current route: 2
          Previous route: 2147483647
          Saving best route, dp[4] = 2
       amount: 5
       amount: 6
          Current route: 3
          Previous route: 2147483647
          Saving best route, dp[6] = 3
       amount: 7
          Current route: 2
          Previous route: 2147483647
          Saving best route, dp[7] = 2
       amount: 8
          Current route: 4
          Previous route: 2147483647
          Saving best route, dp[8] = 4
       amount: 9
          Current route: 3
          Previous route: 2147483647
          Saving best route, dp[9] = 3
       amount: 10
          Current route: 5
          Previous route: 2
          Saving best route, dp[10] = 2
       amount: 11
          Current route: 4
          Previous route: 2147483647
          Saving best route, dp[11] = 4
    
    Coin: 1
       amount: 1
          Current route: 1
          Previous route: 2147483647
          Saving best route, dp[1] = 1
       amount: 2
          Current route: 2
          Previous route: 1
          Saving best route, dp[2] = 1
       amount: 3
          Current route: 2
          Previous route: 2147483647
          Saving best route, dp[3] = 2
       amount: 4
          Current route: 3
          Previous route: 2
          Saving best route, dp[4] = 2
       amount: 5
          Current route: 3
          Previous route: 1
          Saving best route, dp[5] = 1
       amount: 6
          Current route: 2
          Previous route: 3
          Saving best route, dp[6] = 2
       amount: 7
          Current route: 3
          Previous route: 2
          Saving best route, dp[7] = 2
       amount: 8
          Current route: 3
          Previous route: 4
          Saving best route, dp[8] = 3
       amount: 9
          Current route: 4
          Previous route: 3
          Saving best route, dp[9] = 3
       amount: 10
          Current route: 4
          Previous route: 2
          Saving best route, dp[10] = 2
       amount: 11
          Current route: 3
          Previous route: 4
          Saving best route, dp[11] = 3
    

    After iterating through all coins, dp[amount] either:

    1. Contains the shortest coin-path to amount, or
    2. is Integer.MAX_VALUE, indicating that no coin-path to amount was found.

    Below is OP's code, with comments, and with the print statements that generated the above narration:

    public class Solution {
        
        /**
         * Given `coins`, an integer array representing the denominations of coins
         * that you have available, return the **fewest** number of coins in those
         * denominations needed to equal the `amount`.
         * 
         * Ex. coinChange([1, 2, 5], 11) returns 3, since 5 + 5 + 1 = 11.
         * Ex. coinChange([2], 3) returns -1
         * 
         * @param coins The denominations available for summing to `amount`
         * @param amount The amount to reach by different combinations of coins
         * @return The fewest number of coins needed to equal the amount.
         *         -1 if no combination of coins of the given denominations can
         *          equal `amount`.
         */
        public int coinChange(int[] coins, int amount) {
            
            // Handle invalid input
            if (amount < 1) return 0;
            
            /**
             * Initialize an array of amounts (up to and including `amount`),
             * which stores the smallest number of coins yet found to get to
             * that index-amount.
             */
            int[] dp = new int[amount + 1]; 
            
            // Use MAX_VALUE to indicate no discovered "route" to this `amount`
            Arrays.fill(dp, Integer.MAX_VALUE);
            
            // This index's value will never change
            dp[0] = 0;
            
            // For each denomination
            for (int coin : coins) {
                System.out.println("\nCoin: " + coin);
                
                // See if the amount `i` can be reached by one more of this coin
                for (int i = coin; i <= amount; i++) {
                    System.out.println("   amount: " + i);
                    
                    /** 
                     * The amount `i` can be reached by one more of this coin
                     * if there is a discovered "route" to the amount `i - coin`
                     */
                    if (dp[i - coin] != Integer.MAX_VALUE) {
                        System.out.println("      Current route: " + (dp[i - coin] + 1));
                        System.out.println("      Previous route: " + dp[i]);
                        
                        /** 
                         * Compare this "route" to the previous "route," and
                         * keep the better one.
                         */
                        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                        System.out.println("      Saving best route, dp[" + i + "] = " + dp[i]);
                    }
                }
            }
        /** 
         * If we didn't find a "route" to `amount`, return -1.
         * If we did find a "route" to `amount`, the shortest "route" is
         * already stored in dp[amount], so return dp[amount].
         */
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
        }
        
        /**
         * @param args the command line arguments
         */
        public static void main(String[] args) {
            Solution sol = new Solution();
            int coins[] = {5, 2, 1};
            System.out.println(sol.coinChange(coins, 11));
        }   
    }
    

    This algorithm must iterate through each coin in coins, and each of those iterations is the length of amount - coin.
    In the worst case, the largest coin << amount, and time complexity approaches O(amount * coins.length)


  • 0
    D

    I believe your solution goes k times of n ( k is the length of coin array and n is the value of amount)
    If k and n both getting larger, it will take much longer time to run.


Log in to reply
 

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