Number of Ways to Represent N Cents II

Description

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent),

Calculate the minimum number of coins of representing n cents.

Example
n = 11
11 = 1 + 1 + 1... + 1
   = 1 + 1 + 1 + 1 + 1 + 1 + 5
   = 1 + 5 + 5
   = 1 + 10
return 2

Challenge:
what if we only have abnormal coins such as 10 20 50?

what if we cannot find a way to match the number?
such as coins = [10, 20, 50], we want to match 65

What if we want to output the combination of minimum number of coins? (maybe multiple result) We can get the number first, then dfs/bfs finding the combination

Link(dont have)

Lintcode_ladder

Method

1. first dp to test whether we can find a way to present second dp to test what's the minimum number of coins
2. x

Example

1. 1

class Solution {
public:
  int waysNCents(int n) {
        if (n < 0) {
            return 0;
        }
        vector<int> coins = {10, 20, 50};
        // first dp test whether we can find a combination presenting "n"
        vector<int> dp(n+1, 0);
        // starter, when rest volume = 0
        dp[0] = 1;
        int len = coins.size();
        for (int index = 0; index < len; ++index) {
            for (int volume = 1; volume <= n; ++volume) {
                // if we can choose current coin, add one method
                if (volume >= coins[index]) {
                    dp[volume] += dp[volume-coins[index]];
                }
            }
        }
        // test whether we can find a result
        if (dp[n] == 0) {
            return 0;   
        }
        // second dp test the minimum number of coins we need
        vector<int> nums(n+1, 0);
        nums[0] = 0;
        for (int index = 0; index < len; ++index) {
            for (int volume = 1; volume <= n; ++volume) {
                if (volume >= coins[index]) {
                    if (nums[volume] == 0) {
                        nums[volume] = nums[volume-coins[index]] + 1;
                    } else {
                        nums[volume] = 
                            min(nums[volume], nums[volume-coins[index]] + 1);
                    }
                }
            }
        }
        return nums[n];
        // for the future, if we need the actually combination of coins
        // we can perform bfs/dfs to find it out
    }
};

Similar problems

x

Tags

x