This is a classical Dynamic Programming problem, and to solve it we must find the recurrence function between states.

So we can define a function/state ** f[i][v]**, which is the minimum number of coins used to sum up to

**, and**

*v***is the number of different denominations used for this sum (use the first**

*i***denominations in**

*i***).**

*coins**f[i][v] = min {case1, case2}*

** Case1** is

**, where coins[i] isn't used;**

*f[i-1][v]*** Case2** is

**, where coins[i] is used (and can be used multiple times)**

*f[i][v-coins[i-1]]+1*So the weight-lifting work is now finished, and all we have to do is to iterate ** i** from

**to**

*1***(set**

*coins.size()***to 0, obviously), while for each**

*count[0]***we update**

*i***from**

*coins[v]***to**

*v=cost[i-1]***(no need to start from**

*v=amount***, because**

*v=0***is meaningful only when**

*count[v-coins[i-1]]*

*v-coins[i-1]>0*After finishing all this, return count[amount] as the final result (if ** count[amouint]** is still INT_MAX, which means the search fails, then return -1)

```
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int count[amount+1]; // count[v] is minimum coin count that can add up to v
count[0] = 0; // Target value 0 can always be achieved by using no coin at all
for (int i=1;i<=amount;i++)
count[i] = INT_MAX;
for (int j=1;j<=coins.size();j++) { // Use the first j kinds of coins (each kind can be used more than once)
for (int v=coins[j-1];v<=amount;v++) { // If current v is less than coins[i], then we have only one cadidate count[v] and don't need to compare
count[v] = min(count[v], (count[v-coins[j-1]])==INT_MAX?INT_MAX:(count[v-coins[j-1]]+1)); // If count[v-coins[j-1]] is already INT_MAX, then +1 will make it negative, and save this negative value as the new count[v]. Thus add an additional contion to prevent that.
}
}
if (count[amount] == INT_MAX)
return -1;
return count[amount];
}
};
```