# [Java] Shortest and Easy-To-Understand DP solution, O(mn) time, O(n) space

• The idea is simple, think of the optimal structure in terms of the suboptimal problem:

1. If the function `int coinChange(int[] coins, int m, int amount)` means the minimum number of coins used with mth coin.
2. Then we can think of the problem in terms of its suboptimal structures
• The minimum number of coins needed without mth is `coinChange(coins, m - 1, amount)`
• The minimum number of coins needed with mth is `coinChange(coins, m, amount - coins[m]) + 1`
3. Therefore, if we sort the coin by value, the overall minimum result is for every coin[m] included, `min(coinChange(coins, m, amount - coins[m]) + 1)`, since the "not included" case is considered already in previous iterations.

The code below is the iterative solution, slightly different from the recursive thinking process:

``````   public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.sort(coins);
Arrays.fill(dp, -1); //initialize dp table, if it is -1, means no previous coin combination can make the change
dp[0] = 0; //base case

for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
//if the amount without coin can be made, then we add this coin, so the count + 1
if (dp[j - coin] != -1) {
dp[j] = dp[j] == -1 ? dp[j - coin] + 1 : Math.min(dp[j], dp[j - coin] + 1);
}
}
}
return dp[amount];

}``````

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