322. Coin Change

February 2019 2 minute read

Problem

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.

Solution

Use Dynamic Programming.

There is a one dimension table.

For example:

coins = [1,3,5]

amount = 11

Amount Combination
0 0
1 1+dp[0]
2 1+dp[1]
3 min(1+dp[0],1+dp[2])
4 min(1+dp[3],1+dp[1])

A(n) = min(1+dp[n-1],1+dp[n-3],1+dp[n-5])

Code

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [-1 for _ in range(amount + 1)]
        dp[0] = 0
        for i in range(amount + 1):
            for coin in coins:
                if (i - coin) >= 0 and dp[i - coin] >= 0:
                    if dp[i] == -1:
                        dp[i] = dp[i - coin] + 1
                    else:
                        dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[amount]
class Solution
{
public:
  int coinChange(vector<int> &coins, int amount)
  {
    vector<int> dp(amount + 1, -1);
    dp[0] = 0;
    for (int v = 0; v <= amount; v++)
    {
      for (int i = 0; i < coins.size(); i++)
      {
        if ((v - coins[i] >= 0) && (dp[v - coins[i]] != -1))
        {
          if (dp[v] == -1)
          {
            dp[v] = dp[v - coins[i]] + 1;
          }
          else
          {
            dp[v] = min(dp[v], dp[v - coins[i]] + 1);
          }
        }
      }
    }
    return dp[amount];
  }
};