**Problem**

You are given an integer vector (or array) `coins[n]`

representing coins of different denominations and an integer **amount** representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`

. You could assume to have an infinite number of each kind of coin.

###### Input

int vector: `coins[n]`

, int: `amount`

###### Output

an integer representing fewest number of coins that you need to make up amount

###### Constraints

`1 <= coins.length <= 12`

`1 <= coins[i] <= 2`

^{31}- 1`0 <= amount <= 10`

^{4}

###### Sample Input

coins = [1,2,5], amount = 11

###### Sample Output

3 Explanation: 11 = 5 + 5 + 1

###### Solution

This problem could be solved in polynomial time using Dynamic programming.

###### Dynamic Programming

**Optimal Substructure**

An optimal solution to problem contain optimal solution to subproblems. To consider all kinds of coins,** 2 cases for every coin arises:**

`coin[i]`

is included in the optimal set`coin[i]`

is not included in the optimal set

Therefore, minimum number of coins needed to make the given **amount** **j** is minimum of the following:

- Minimum number of coins required to obtain
**amount (j)**using`coins[0..i]`

. (`coin[i]`

is not included) - Minimum number of coins required to obtain
**amount (j – coins[i])**using`coins[0..i] + 1`

. (`coin[i]`

is included)

dp[j] represents the minimum number of coins that you need to make up amount j Now according to optimal substructure: for i = 0 to coins.size()-1: for j = coins[i] to amount: dp[j] = min (dp[j], dp[j-coins[i]]+1)

**Base case & Initialisation**

dp[0] = 0, minimum number of coins required to make sum = 0, is 0 dp[j] = INT_MAX, if j > 0

###### Code Implementation

```
int coinChange(vector<int>& coins, int amount) {
int *dp = new int[amount+1]();
dp[0] = 0;
for (int i=1; i<=amount; i++) {
//(- 1)To prevent Integer Overflow
dp[i] = INT_MAX-1;
}
for (int i=0; i<coins.size(); i++) {
for (int j=coins[i]; j<=amount; j++) {
dp[j] = min (dp[j], dp[j-coins[i]]+1);
}
}
return dp[amount] == INT_MAX-1 ? -1 : dp[amount];
}
```

**Time complexity of the above solution is O(N*amount) (N is the size of coins vector) and auxiliary space required is O(amount).**