Coin Change, a Dynamic Programming problem, by LeetCode

-
Here it is: https://leetcode.com/problems/coin-change/description/

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:
Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
Same cues again that this is a DP problem: asking for the fewest number of combinations (not the combinations themselves), exponential in nature if you were to compute all permutations. Now it was not said how large "amount" can be, but assume that it is a reasonable value (say <= 1000000). We can find a solution to this problem in O(amount * len(coins))-time and O(amount)-space using DP.
The idea with DP again is to construct the solution from 0,1,2... all the way to amount. Suppose that you're computing the solution for N. And assume that you have 3 coins C1, C2 and C3 (you can generalize later). To get to N, inevitably you'll have to get to either N-C1, or N-C2 or N-C3. Compute the min out of those, add 1. Keep doing that until you reach amount. That's it! Code is below, cheers, Boris.


public class Solution
{
 public int CoinChange(int[] coins, int amount)
 {
  //Base
  if (amount < 0) return -1;
  if (amount == 0) return 0;

  //Induction DP
  int[] minChange = new int[amount + 1];

  for (int i = 1; i <= amount; i++)
  {
   int min = Int32.MaxValue;
   for (int j = 0; j < coins.Length; j++)
    if (i - coins[j] >= 0 && minChange[i - coins[j]] != -1 && minChange[i-coins[j]] + 1 < min)
     min = minChange[i - coins[j]] + 1;
   minChange[i] = (min == Int32.MaxValue) ? -1 : min;
  }

  return minChange[amount];
 }
}

Comments

  1. TarasDecember 23, 2018 at 2:19 PM

    Classics of DP :) My solution is more verbose because it keeps only 2 rows instead of entire matrix in memory, but the idea is the same.

    class Solution {
    public:
    int coinChange(vector& coins, int amount) {
    vector> d(2, vector(amount+1, amount+1));
    d[0][0] = 0;
    bool prev = 0;
    bool current = 1;
    for (int c = 1; c <= coins.size(); ++c) {
    d[current][0] = 0;
    for (long a = 1; a <= amount; ++a) {
    if (coins[c-1] <= a) {
    d[current][a] = min(1 + d[current][a-coins[c-1]], d[prev][a]);
    } else {
    d[current][a] = d[prev][a];
    }
    }
    prev = !prev;
    current = !current;
    }
    auto min_coins = d[prev][amount];
    return min_coins == amount+1 ? -1 : min_coins;
    }
    };

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more