Coin Change Solutions in C++

// Source : https://leetcode.com/problems/coin-change/
// Author : Calinescu Valentin, Hao Chen
// Date   : 2015-12-28




/* Recursive solution - TIME LIMIT ERROR */
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {  
        int result = INT_MAX;
        if ( amount == 0 ) return 0;
        if ( amount < 0 ) return -1;
        for (int i=0; i<coins.size(); i++) {
            if ( amount - coins[i] < 0 ) continue;
            int r = coinChange(coins, amount - coins[i]);
            if ( r == -1 ) continue;
            if (result > r )  result = r + 1;
        }
        return result == INT_MAX ? -1 : result;
    }
}


 /* 
 * Solution 1 - O(N * amount)
 * =========
 *
 * This problem can be solved using dynamic programming, thus building the optimal
 * solution from previous smaller ones. For every coin of value t and every sum of money
 * i the sum can be traced back to a previous sum i - t that was already computed and uses
 * the smallest number of coins possible. This way we can construct every sum i as the
 * minimum of all these previous sums for every coin value. To be sure we'll find a minimum
 * we can populate the solution vector with an amount bigger than the maximum possible, 
 * which is amount + 1(when the sum is made up of only coins of value 1). The only exception
 * is sol[0] which is 0 as we need 0 coins to have a sum of 0. In the end we need to look
 * if the program found a solution in sol[amount] or it remained the same, in which case we
 * can return -1.
 * 
 */
class Solution {
public:
    
    int coinChange(vector<int>& coins, int amount) {
        int sol[amount + 1];
        sol[0] = 0;
        for(int i = 1; i <= amount; i++)
            sol[i] = amount + 1;
        for(int i = 0; i < coins.size(); i++)
        {
            for(int j = coins[i]; j <= amount; j++)
                sol[j] = min(sol[j], sol[j - coins[i]] + 1);
        }
        if(sol[amount] != amount + 1)
            return sol[amount];
        else
            return -1;
    }
};


//Another DP implmentation, same idea above 
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        const int MAX = amount +1;
        vector<int> dp(amount+1, MAX);
        dp[0]=0;
        
        for(int i=1; i<=amount; i++) {
            for (int j=0; j<coins.size(); j++){
                if (i >= coins[j]) {
                    dp[i] = min( dp[i], dp[i-coins[j]] + 1 );
                }
            }
        }

        return dp[amount]==MAX ? -1 : dp[amount];
    }
};

/// Source : https://leetcode.com/problems/coin-change/solution/
/// Author : liuyubobobo
/// Time   : 2018-03-08

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/// Memory Search
///
/// Time Complexity: O(coins_size * amount)
/// Space Complexity: O(amount)
class Solution {

private:
    vector<int> dp;
    int max_amount;

public:
    int coinChange(vector<int>& coins, int amount) {
        max_amount = amount + 1;
        dp = vector<int>(amount+1, -1);
        int res = search(coins, amount);
        return res == max_amount ? -1 : res;
    }

private:
    int search(const vector<int>& coins, int amount){

        if(amount == 0)
            return 0;

        if(dp[amount] != -1)
            return dp[amount];

        int res = max_amount;
        for(int coin: coins)
            if(amount - coin >= 0)
                res = min(res, 1 + search(coins, amount -coin));
        return dp[amount] = res;
    }
};


int main() {

    vector<int> coins1 = {1, 2, 5};
    int amount1 = 11;
    cout<< Solution().coinChange(coins1, amount1) << endl;
    // 3

    // ---

    vector<int> coins2 = {2};
    int amount2 = 1;
    cout << Solution().coinChange(coins2, amount2) << endl;
    // -1

    // ---

    vector<int> coins3 = {2};
    int amount3 = 3;
    cout << Solution().coinChange(coins3, amount3) << endl;
    // -1

    // ---

    vector<int> coins4 = {2, 5, 10, 1};
    int amount4 = 27;
    cout << Solution().coinChange(coins4, amount4) << endl;
    // 4

    // ---

    vector<int> coins5 = {186, 419, 83, 408};
    int amount5 = 6249;
    cout << Solution().coinChange(coins5, amount5) << endl;
    // 20

    return 0;
}

/// Source : https://leetcode.com/problems/coin-change/solution/
/// Author : liuyubobobo
/// Time   : 2018-03-08

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Problem
/// 0-1 backpack problem
///
/// Time Complexity: O(coins_size * amount)
/// Space Complexity: O(amount)
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

        vector<int> dp(amount+1, amount + 1);
        dp[0] = 0;

        for(int coin: coins)
            for(int j = coin ; j <= amount ; j ++)
                dp[j] = min(dp[j], dp[j-coin] + 1);

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};


int main() {

    vector<int> coins1 = {1, 2, 5};
    int amount1 = 11;
    cout<< Solution().coinChange(coins1, amount1) << endl;
    // 3

    // ---

    vector<int> coins2 = {2};
    int amount2 = 1;
    cout << Solution().coinChange(coins2, amount2) << endl;
    // -1

    // ---

    vector<int> coins3 = {2};
    int amount3 = 3;
    cout << Solution().coinChange(coins3, amount3) << endl;
    // -1

    // ---

    vector<int> coins4 = {2, 5, 10, 1};
    int amount4 = 27;
    cout << Solution().coinChange(coins4, amount4) << endl;
    // 4

    // ---

    vector<int> coins5 = {186, 419, 83, 408};
    int amount5 = 6249;
    cout << Solution().coinChange(coins5, amount5) << endl;
    // 20

    return 0;
}

/// Source : https://leetcode.com/problems/coin-change/solution/
/// Author : liuyubobobo
/// Time   : 2018-03-08

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Problem
/// 0-1 backpack problem
///
/// Time Complexity: O(coins_size * amount)
/// Space Complexity: O(amount)
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        for(int i = 1 ; i <= amount ; i ++)
            for(int coin: coins)
                if(i - coin >= 0)
                    dp[i] = min(dp[i], dp[i-coin] + 1);

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};


int main() {

    vector<int> coins1 = {1, 2, 5};
    int amount1 = 11;
    cout<< Solution().coinChange(coins1, amount1) << endl;
    // 3

    // ---

    vector<int> coins2 = {2};
    int amount2 = 1;
    cout << Solution().coinChange(coins2, amount2) << endl;
    // -1

    // ---

    vector<int> coins3 = {2};
    int amount3 = 3;
    cout << Solution().coinChange(coins3, amount3) << endl;
    // -1

    // ---

    vector<int> coins4 = {2, 5, 10, 1};
    int amount4 = 27;
    cout << Solution().coinChange(coins4, amount4) << endl;
    // 4

    // ---

    vector<int> coins5 = {186, 419, 83, 408};
    int amount5 = 6249;
    cout << Solution().coinChange(coins5, amount5) << endl;
    // 20

    return 0;
}