You are given an integer array bills representing bills of different denominations and an integer amount representing a total amount of money.
Return the fewest number of bills that you need to make up that amount. If that amount of money cannot be made up by any combination of the bills, return -1.
You may assume that you have an infinite number of each kind of bill.
Example 1:
Input: bills = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1Example 2:
Input: bills = [2], amount = 3
Output: -1Example 3:
Input: bills = [1], amount = 0
Output: 0Example 4:
Input: bills = [1,15,25], amount = 30
Output: 2This is the classic coin change problem: given unlimited bills of certain denominations, find the minimum number needed to make up a target amount, or return -1 if it is impossible. The standard solution is dynamic programming, where <code>dp[i]</code> stores the minimum bills needed for amount <code>i</code>, and each denomination is used to relax the transition. The examples highlight both reachable and unreachable cases, such as [1,2,5] making 11 with 3 bills, and [2] making 3 being impossible.
