118: Coin change

Given an array of coins of different denominations and a total amount of money, return the fewest number of coins that you need to make up the given total amount. Return -1 if impossible to make up the given amount

 

Example 1

Input:  coins = [5, 7, 9] amount = 8

Output: -1

Example 2

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

Output: 3

Explanation: 1 + 5 + 5