# Two similar solutions but one is much more faster. (C++ recursive and dp solution)

• solution 1 and solution 2 are almost the same except the data structure used
• but why is solution2 so slow? just because I used the `unordered_map`?

solution 1(124ms)

recursive and dp with `array`:

``````class Solution {
public:
int* dp;

int recur(vector<int>& coins, int amount) {
if (amount < 0) return -1;
if (dp[amount] != INT32_MAX) return dp[amount];
for (int i = 0; i < coins.size(); ++i){
int temp = recur(coins, amount - coins[i]);
if (temp >= 0) dp[amount] = min(dp[amount], temp + 1);
}
if (dp[amount] == INT32_MAX) dp[amount] = -1;
return dp[amount];
}

int coinChange(vector<int>& coins, int amount) {
dp = new int[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; ++i){
dp[i] = INT32_MAX;
}
return recur(coins, amount);
}
};
``````

solution 2(1752ms)

recursive and dp with `unordered_map`

``````class Solution {
public:
unordered_map<int, int> dp;

int recur(vector<int>& coins, int amount) {
if (amount < 0) return -1;
if (dp.find(amount) != dp.end()) return dp[amount];
int cur = INT32_MAX;
for (int i = 0; i < coins.size(); ++i){
int temp = recur(coins, amount - coins[i]);
if (temp >= 0) cur = min(cur, temp + 1);
}
if (cur > 0 && cur != INT32_MAX)
return dp[amount] = cur;
else
return dp[amount] = -1;
}

int coinChange(vector<int>& coins, int amount) {
dp[0] = 0;
return recur(coins, amount);
}
};
``````

solution 3(152ms)

iterative and dp

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int dp[amount + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= amount; ++i){
dp[i] = INT32_MAX;
for (auto coin : coins){
if (i >= coin && dp[i - coin] != -1){
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
if (dp[i] == INT32_MAX) dp[i] = -1;
}
return dp[amount];
}
};``````

• This post is deleted!

• @xidui when you already have the amounts in kind of sorted order why use unordered_map ? Just asking.

BTW good job with the solution (Y).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.