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

- If the function
`int coinChange(int[] coins, int m, int amount)`

means the minimum number of coins used withcoin.**mth** - Then we can think of the problem in terms of its suboptimal structures
- The minimum number of coins needed without
is**mth**`coinChange(coins, m - 1, amount)`

- The minimum number of coins needed with
is**mth**`coinChange(coins, m, amount - coins[m]) + 1`

- The minimum number of coins needed without
- Therefore, if we sort the coin by value, the overall minimum result is
, since the**for every coin[m] included,**`min(coinChange(coins, m, amount - coins[m]) + 1)`

*"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];
}
```