Java DP solution, sorting coins array to speed up


  • 0
    Y

    sorting coins array into ascending order so that we can early termination.

      public class Solution {
            public int coinChange(int[] coins, int amount) {
                // DP, time complexity: O(ClogC + amount / smallest_coin), C = |coins|
                // space complexity: O(amount)
                // opt[i] = min_j(opt[j]) + 1 if j - i is a denomination in coins
                Arrays.sort(coins);
                int[] opt = new int[amount + 1];
                opt[0] = 0;
                for (int i = 1; i <= amount; i++) {
                    opt[i] = Integer.MAX_VALUE;
                    for (int c : coins) {
                        if (i >= c) {
                            if (opt[i - c] != Integer.MAX_VALUE) {
                                opt[i] = Math.min(opt[i], opt[i - c] + 1);
                            }
                        } else {
                            break;
                        }
                    }
                }
                return opt[amount] == Integer.MAX_VALUE ? -1 : opt[amount];
            }
        }

  • 0
    E

    You may want to edit your answer a little bit so it is more readable :)


  • 0
    Y

    thanks! I just did that.


Log in to reply
 

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