[C++] Leetcode 322. Coin Change (Hint, Solution)

Problem

https://leetcode.com/problems/coin-change

Coin Change - LeetCode

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return 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.

You may assume that you have an infinite number of each kind of coin.

 

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

Example 3:

Input: coins = [1], amount = 0
Output: 0

 

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

 

 

 

 

Hint

Try using Dynamic Programming Tabulation.

 

 

 

Solution

This can be solved with below three method
1. Recursion + Memoization
2. Tabulation

 

 

Code

Simple

1. Recursion + Memoization

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        unordered_map<int, int> dp;
        dp[0] = 0;
        for (int coin : coins)
            dp[coin] = 1;
        sort(coins.rbegin(), coins.rend());
        int answer = recursive(amount, coins, dp);

        return answer;
    }
    int recursive(int amount, vector<int>& coins, unordered_map<int, int> &dp) {
        if (amount < 0) {
            return -1;
        } else if (amount == 0) {
            return 0;
        } else if (dp.count(amount)) {
            return dp[amount];
        } else {
            dp[amount] = INT_MAX;
            for (int coin : coins) {
                int combination = recursive(amount-coin, coins, dp) + 1;
                if (dp[amount] > combination && combination > 0)
                    dp[amount] = combination;
            }
            dp[amount] = dp[amount] == INT_MAX ? -1 : dp[amount];
            return dp[amount];
        }
    }
};

2. Tabulation

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+1; i++) {
            for (int coin : coins) {
                if (i-coin > -1)
                    dp[i] = min(dp[i], dp[i-coin]+1);
            }
        }
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
};

 

Whole Code with Test Case

// https://leetcode.com/problems/coin-change
#include <iostream>
#include <vector>

using namespace std;

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+1; i++) {
            for (int coin : coins) {
                if (i-coin > -1)
                    dp[i] = min(dp[i], dp[i-coin]+1);
            }
        }
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
};

int main() {
    Solution s = Solution();
    vector<int> coins = {4,7};
    cout << s.coinChange(coins, 6) << endl;
    cout << endl;
}

 

 

 

Complexity

Time

Time complexity will be O(n * amount).

 

Space

Space complexity will be O(amount).

 

 

 

Best Solution (Pinned)

 

 

 

Overall and Tips

Result

1. Recursion + Memoization

2. Tabulation

 

Tips

Try using an array and assign it manually than using a vector initializer.
This somehow helps runtime get faster.

For example, initialize vector like this:

int dp[amount+1];
for (int i = 0; i < amount+1; i++) {
	dp[i] = amount+1;
}

than this:

vector<int> dp(amount + 1, amount + 1);

Please comment if you know why this happens!