Coin Change 2 Solutions in C++

// Source : https://leetcode.com/problems/coin-change-2/
// Author : Hao Chen
// Date   : 2019-03-18


class Solution {
public:
    int change(int amount, vector<int>& coins) {
        return change_dp(amount, coins);
        return change_recursive(amount, coins); // Time Limit Error
    }
    
    
    int change_recursive(int amount, vector<int>& coins) {
        int result = 0;
        change_recursive_helper(amount, coins, 0, result);
        return result;
    }
    
    // the `idx` is used for remove the duplicated solutions.
    void change_recursive_helper(int amount, vector<int>& coins, int idx, int& result) {
        if (amount == 0) { 
            result++; 
            return;
        }
    
        for ( int i = idx; i < coins.size(); i++ ) {
            if (amount < coins[i]) continue;
            change_recursive_helper(amount - coins[i], coins, i, result);
        }
        return;
    }
    
    int change_dp(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for (int i=0; i<coins.size(); i++) {
            for(int n=1; n<=amount; n++) {
                if (n >= coins[i]) {
                    dp[n] += dp[n-coins[i]];
                }
            }
        }

        return dp[amount];
    }
};

/// Source : https://leetcode.com/problems/domino-and-tromino-tiling/description/
/// Author : liuyubobobo
/// Time   : 2018-03-08

#include <iostream>
#include <vector>

using namespace std;


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

private:
    vector<vector<int>> dp;

public:
    int change(int amount, vector<int>& coins) {

        dp = vector<vector<int>>(coins.size(), vector<int>(amount + 1, -1));
        int res = search(coins, 0, amount);
        return res == -1 ? 0 : res;
    }

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

        if(index == coins.size())
            return amount == 0 ? 1 : 0;

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

        int res = 0;
        for(int i = 0 ; i * coins[index] <= amount ; i ++)
            res += search(coins, index + 1, amount - i * coins[index]);
        return dp[index][amount] = res;
    }
};

int main() {

    vector<int> coins1 = {1, 2, 5};
    cout << Solution().change(5, coins1) << endl;

    vector<int> coins2 = {2};
    cout << Solution().change(3, coins2) << endl;

    vector<int> coins3 = {10};
    cout << Solution().change(10, coins3) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/domino-and-tromino-tiling/description/
/// Author : liuyubobobo
/// Time   : 2018-03-08

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
///
/// Time Complexity: O(len(coins)*amount*log(amount))
/// Space Complexity: O(len(coins)*amount)
class Solution {

public:
    int change(int amount, vector<int>& coins) {

        vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, 0));
        dp[coins.size()][0] = 1;
        for(int i = coins.size() - 1; i >= 0 ; i --)
            for(int j = 0; j <= amount; j ++)
                for(int k = 0 ; k * coins[i] <= j ; k ++)
                    dp[i][j] += dp[i + 1][j - k * coins[i]];
        return dp[0][amount];
    }
};

int main() {

    vector<int> coins1 = {1, 2, 5};
    cout << Solution().change(5, coins1) << endl;

    vector<int> coins2 = {2};
    cout << Solution().change(3, coins2) << endl;

    vector<int> coins3 = {10};
    cout << Solution().change(10, coins3) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/domino-and-tromino-tiling/description/
/// Author : liuyubobobo
/// Time   : 2018-03-08

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
///
/// Time Complexity: O(len(coins)*amount)
/// Space Complexity: O(amount)
class Solution {

public:
    int change(int amount, vector<int>& coins) {

        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for(int i = coins.size() - 1; i >= 0 ; i --)
            for(int j = coins[i]; j <= amount; j ++)
                dp[j] += dp[j - coins[i]];
        return dp[amount];
    }
};

int main() {

    vector<int> coins1 = {1, 2, 5};
    cout << Solution().change(5, coins1) << endl;

    vector<int> coins2 = {2};
    cout << Solution().change(3, coins2) << endl;

    vector<int> coins3 = {10};
    cout << Solution().change(10, coins3) << endl;

    return 0;
}