# My C++ dynamic programming solution with explaination

• (1) you should sort coins.(record the smallest)

(2) traverse the result vector from the smallest coin

(3) result[i] = result[j] + 1(j < i and exist k that j + coins[k] equals i). otherwise, result[i] = -1

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(!amount)
{
return 0;
}
if(!coins.size())
{
return -1;
}
vector<int> result(amount + 1, -1);
sort(coins.begin(), coins.end());
int start = coins[0];
for(int i = 0; i < coins.size(); i++)
{
if(coins[i] <= amount)
{
result[coins[i]] = 1;
}
}
for(int i = start + 1; i <= amount; i++)
{
int min = INT_MAX;
if(result[i] == 1)
{
continue;
}
for(int k = 0; k < coins.size() && i - coins[k] >= start; k++)
{
if(result[i - coins[k]] != -1)
{
min = min > result[i - coins[k]] + 1 ? result[i - coins[k]] + 1 : min;
}
}
result[i] = min == INT_MAX ? -1 : min;
}
return result[amount];
}
};``````

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