Number of Ways to Represent N Cents(ladder)

Description

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways 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 4

Link

Lintcode_ladder

Method

1. Brute force, combination set, about O(n^4)
2. Dp, backpack, O(4xn), combination without overlapping

Example

1. class Solution {
   public:
    /**
     * @param n an integer
     * @return an integer
     */
    // --------------------------------------------------------------------
    // brute force O(n^4)
    int waysNCents(int n) {
        // Write your code here
        if (n < 1) {
            return -1;
        }
        int result = 0;
        vector<int> coins = {1, 5, 10 ,25};
        helper(0, n, coins, result);
        return result;
    }
    void helper(int index, int target, vector<int>& coins, int& result) {
        if (target == 0) {
            result++;
        }
        int len = coins.size();
        int dup = -1;
        for (int i = index; i < len; ++i) {
            int rest = target - coins[i];
            // pruning
            if (rest < 0) {
                break;
            }
            // de-dup
            if (dup != -1 && dup == coins[i]) {
                continue;
            }
            helper(i, rest, coins, result);
            dup = coins[i];
        }
        return;
    }
    // ----------------------------------------------------------------------
     // simplified, back pack O(4*N)
    // Perform: combination without overlapping
    //
    // Imp:
    // coins outer:
    // volume internal:
    // For example,
    // pack = 3, coins = 1, 2, 3
    // dp index: [0,  1,  2,  3]
    // init   :   1
    // coins 1:      +1  +1  +1
    // coins 2:          +1  +1    
    // coins 3:              +1
    //
    // As we can see, when consider coins = 2, pack = 3, 
    // we just +1 to dp[3] instead of +2, 
    // we would consider that coins = 2 can replace 2 of coins = 1,
    // So we didnot care the sequence , Therefore it is combination
    int waysNCents(int n) {
        if (n < 0) {
            return 0;
        }
        vector<int> dp(n+1, 0);
        vector<int> coins = {1, 5, 10 ,25};
        // 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]];
                }
            }
        }
        return dp[n];
    }
   };
   

Similar problems

backpack

Tags

DP, permutation