Problem library

Shop Change

Medium
dynamic programming
Warm up with this problem Battle on it

The in-game shop pays out change using tokens whose values are listed in tokens (you have an unlimited number of each). Return the smallest number of tokens that add up to exactly amount, or -1 if it cannot be done. An amount of 0 needs 0 tokens.

Examples

Input: tokens = [1,5,12], amount = 15
Output: 3
Input: tokens = [4,6], amount = 7
Output: -1