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];
}
DP AC JAVA Solution 18ms Beating 95%


@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.

@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..

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

This solution is mysterious at first, but I like thinking of it as finding the shortest coinpath 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 of11
: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: Contains the shortest coinpath to
amount
, or  is
Integer.MAX_VALUE
, indicating that no coinpath toamount
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 indexamount. */ 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
incoins
, and each of those iterations is the length ofamount  coin
.
In the worst case, the largestcoin
<<amount
, and time complexity approachesO(amount * coins.length)
 Contains the shortest coinpath to