# c++ dp(46ms) solution and BFS(26ms) solution

• dp solution:

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int len=coins.size();
vector<int> dp(amount+1, INT_MAX);
dp[0]=0;
for(int i=1; i<=amount; i++)
{
for(int j=0; j<len; j++)
{
int val=i-coins[j];
if(val>=0 && dp[val] != INT_MAX)
dp[i]=min(dp[i], 1+dp[val]);
}
}
return dp[amount]==INT_MAX?-1:dp[amount];
}
};
``````

BFS solution. visited vector to record the amount being visited is the key to save the time

`````` int coinChange(vector<int>& coins, int amount) {
int len=coins.size();
if(amount<0)
return -1;
if(amount==0)
return 0;
vector<int> visited(amount+1, false);
int level=0;
int ans=INT_MAX;
queue<int> Q;
Q.push(amount);
visited[amount]=true;
while(!Q.empty())
{
int sz=Q.size();
++level;
for(int i=0; i<sz; i++)
{

int temp=Q.front();
Q.pop();
for(int i=0; i<len; i++)
{
int val=temp-coins[i];
if(val==0)
{
ans=min(ans, level);
}
if(val>0 && visited[val]==false)
{
visited[val]=true;
Q.push(val);
}
}
}
}
return ans==INT_MAX?-1:ans;
}
``````

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