Coin Change: the idea to remember.

The core insight

For each amount, try taking each feasible final coin and add one to the best smaller amount.

Why it works

An optimal nonempty combination has a final coin; removing it leaves an optimal subproblem or we could improve the original.

The mistake to avoid

Initialize unreachable states above any possible answer, and set dp[0]=0. A greedy largest coin choice is not generally correct.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int value = 1; value <= amount; value++) {
        for (int coin : coins) if (coin <= value)
            dp[value] = Math.min(dp[value], dp[value - coin] + 1);
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Make the next connection