## 322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = , amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

b'
\n\n

## Summary

\n

This article is for intermediate users. It introduces the following ideas:\nBacktracking, Dynamic programming.

\n

## Solution

\n
\n

#### Approach #1 (Brute force) [Time Limit Exceeded]

\n

Intuition

\n

The problem could be modeled as the following optimization problem :\n\n

\n

, where is the amount, is the coin denominations, is the number of coins with denominations used in change of amount . We could easily see that .

\n

A trivial solution is to enumerate all subsets of coin frequencies that satisfy the constraints above, compute their sums and return the minimum among them.

\n

Algorithm

\n

To apply this idea, the algorithm uses backtracking technique to generate all combinations of coin frequencies in the range $[{0, \\frac{S}{c_i}}]$ which satisfy the constraints above. It makes a sum of the combinations and returns their minimum or in case there is no acceptable combination.

\n

Java

\n
public class Solution {    \n\n    public int coinChange(int[] coins, int amount) {\n        return coinChange(0, coins, amount);\n    }\n\n    private int coinChange(int idxCoin, int[] coins, int amount) {\n        if (amount == 0)\n            return 0;\n        if (idxCoin < coins.length && amount > 0) {\n            int maxVal = amount/coins[idxCoin];\n            int minCost = Integer.MAX_VALUE;\n            for (int x = 0; x <= maxVal; x++) {\n                if (amount >= x * coins[idxCoin]) {\n                    int res = coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);\n                    if (res != -1)\n                        minCost = Math.min(minCost, res + x);\n                }                    \n            }           \n            return (minCost == Integer.MAX_VALUE)? -1: minCost;\n        }        \n        return -1;\n    }  \n}\n\n// Time Limit Exceeded\n
\n

Complexity Analysis

\n
\n
• Time complexity : . In the worst case, complexity is exponential in the number of the coins . The reason is that every coin denomination could have at most values. Therefore the number of possible combinations is :
• \n
\n

\n\n

\n
\n
• Space complexity : .\nIn the worst case the maximum depth of recursion is . Therefore we need space used by the system recursive stack.
• \n
\n
\n

#### Approach #2 (Dynamic programming - Top down) [Accepted]

\n

Intuition

\n

Could we improve the exponential solution above? Definitely! The problem could be solved with polynomial time using Dynamic programming technique. First, let\'s define:

\n
\n

\n - minimum number of coins needed to make change for amount using coin denominations \n

\n
\n

We note that this problem has an optimal substructure property, which is the key piece in solving any Dynamic Programming problems. In other words, the optimal solution can be constructed from optimal solutions of its subproblems.\nHow to split the problem into subproblems? Let\'s assume that we know where some change for which is optimal and the last coin\'s denomination is .\nThen the following equation should be true because of optimal substructure of the problem:

\n

\n\n

\n

But we don\'t know which is the denomination of the last coin . We compute for each possible denomination and choose the minimum among them. The following recurrence relation holds:

\n

\n\n

\n

\n\n

\n \n

In the recursion tree above, we could see that a lot of subproblems were calculated multiple times. For example the problem was calculated times. Therefore we should cache the solutions to the subproblems in a table and access them in constant time when necessary

\n

Algorithm

\n

The idea of the algorithm is to build the solution of the problem from top to bottom. It applies the idea described above. It use backtracking and cut the partial solutions in the recursive tree, which doesn\'t lead to a viable solution. \xd0\xa2his happens when we try to make a change of a coin with a value greater than the amount . To improve time complexity we should store the solutions of the already calculated subproblems in a table.

\n

Java

\n
public class Solution {\n\n    public int coinChange(int[] coins, int amount) {        \n        if (amount < 1) return 0;\n        return coinChange(coins, amount, new int[amount]);\n    }\n\n    private int coinChange(int[] coins, int rem, int[] count) {\n        if (rem < 0) return -1;\n        if (rem == 0) return 0;\n        if (count[rem - 1] != 0) return count[rem - 1];\n        int min = Integer.MAX_VALUE;\n        for (int coin : coins) {\n            int res = coinChange(coins, rem - coin, count);\n            if (res >= 0 && res < min)\n                min = 1 + res;\n        }\n        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;\n        return count[rem - 1];\n    }\n}\n
\n

Complexity Analysis

\n
\n
• \n

Time complexity : . where S is the amount, n is denomination count.\nIn the worst case the recursive tree of the algorithm has height of and the algorithm solves only subproblems because it caches precalculated solutions in a table. Each subproblem is computed with iterations, one by coin denomination. Therefore there is time complexity.

\n
• \n
• \n

Space complexity : , where is the amount to change\nWe use extra space for the memoization table.

\n
• \n
\n
\n

#### Approach #3 (Dynamic programming - Bottom up) [Accepted]

\n

Algorithm

\n

For the iterative solution, we think in bottom-up manner. Before calculating , we have to compute all minimum counts for amounts up to . On each iteration of the algorithm is computed as \n

\n \n

In the example above you can see that:

\n

\n\n

\n

Java

\n
public class Solution {\n    public int coinChange(int[] coins, int amount) {\n        int max = amount + 1;             \n        int[] dp = new int[amount + 1];  \n        Arrays.fill(dp, max);  \n        dp = 0;   \n        for (int i = 1; i <= amount; i++) {\n            for (int j = 0; j < coins.length; j++) {\n                if (coins[j] <= i) {\n                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);\n                }\n            }\n        }\n        return dp[amount] > amount ? -1 : dp[amount];\n    }\n}\n
\n

Complexity Analysis

\n
\n
• Time complexity : .\nOn each step the algorithm finds the next in iterations, where . Therefore in total the iterations are .
• \n
• Space complexity : .\nWe use extra space for the memoization table.
• \n
\n

Analysis written by: @elmirap.

\n
'