# My DP (100ms) & BFS (64ms) C++ solutions

• First, BFS solution. In this solution, nodes[cur..curEnd) save all the possible amounts that can be combined with steps coins. For each while loop, we try to extend nodes[cur..curEnd) by adding a new coin to nodes[cur..curEnd). To avoid revisiting nodes that are visited before, an array visited is used to indicate whether the amount i is reached/visited before.

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(amount < 0) return -1;
if(amount ==0) return 0;
bool visited[amount]; // flag to indicate whether the amount i is visited before
fill_n(visited, amount, false);
int nodes[amount], cur=0, curEnd=1, j, newEnd = 1,newN, steps=0;
nodes[0] = 0; //starting from the amount of 0
while(cur<curEnd)
{ // if there are still some amounts that are smaller than "amount" that we can extend by adding a coin
for(++steps;cur<curEnd; ++cur)
{ // extend each nodes at the current level
for(j=0; j<coins.size();++j)
{ // extending by adding a new coin
newN = nodes[cur] + coins[j];
if(newN== amount) // if the new amount is equal to "amount", return steps
return steps;
else if(newN< amount)
{
if(!visited[newN])
{ // if the new amount is not visited before, add to the queue for next while loop
nodes[newEnd++] = newN;
visited[newN] = true;
}
}
}
}
curEnd = newEnd;
}
return -1;
}
``````

};

Then DP algorithm,
Using an array steps to save the minimum coins that can combine together to get "amount", steps[i]=-1 means i can not be reached.

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(amount < 0) return -1;
if(amount ==0) return 0;
int steps[amount+1], res = -1, i, j;
fill_n(steps, amount+1, -1);
for(i=0,steps[i]=0; i<amount;++i)
{
if(steps[i]<0) continue; // if i is not reachable, then skip it.
for(j=0; j<coins.size();++j)
if(i+coins[j]<= amount && (steps[i+coins[j]]<0 || steps[i+coins[j]] > steps[i]+1) )
steps[i+coins[j]] = steps[i]+1; // if the current combination needs less coins, then update it.
}
return steps[amount];
}
};``````

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