# A C++ solution of beginner (includes general idea of DP problems)

• I'm also a beginner.
In my idea, when come to DP problems (such as find the most 'optimum' solution), the first step is to decide use what to make a matrix/column (the element of matrix/column record the 'optimum' step). In this problem, the column is [0, 1, 2,..., amount]. Here we call the column as dp[], it has amount +1 elements.
The second step is to find the relationship among them. In this problem, 'optimum' step of current amount dp[cur] equals to the minimum of dp[cur - 'denominations'] + 1.

``````int coinChange(vector<int>& co, int am)
{
if (!am)
return 0;
if (co.empty())
return -1;
int sz = co.size();
vector<int> dp(am + 1, -1);//initialize the dp[] as -1.
for (auto x : co)
{
if (x <= am)
dp[x] = 1;//set the dp[denomination] equals to 1, because we can use one coin to get the amount of each denomination.
}
for (int i = 1; i <= am; ++i)
{
if (1 == dp[i])//skip the dp[] of each denomination.
continue;
int minsp = INT_MAX;
for (int j = 0; j < sz; ++j)
{
int t = co[j];
if (i - t > 0 && dp[i - t] > 0 && dp[i - t] < minsp)
minsp = dp[i - t];
}
if (minsp != INT_MAX)
dp[i] = minsp + 1;
}
return dp[am];
}
``````

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