TikTok VO 面试真题解析：Coin Change（零钱兑换）

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 + 1

Example 2:

Input: bills = [2], amount = 3
Output: -1

Example 3:

Input: bills = [1], amount = 0
Output: 0

Example 4:

Input: bills = [1,15,25], amount = 30
Output: 2

这道题本质上是经典的零钱兑换问题，要求在给定面额数组和目标金额的情况下，用最少的纸币数凑出指定金额。因为每种面额都可以无限使用，通常会用动态规划来做：定义 <code>dp[i]</code> 表示凑出金额 <code>i</code> 所需的最少纸币数，再枚举每个面额进行状态转移。如果某个金额无法被凑出，就保持为不可达状态，最终返回 <code>-1</code>。题目里的例子也很好地体现了这一点，比如 <code>[1,2,5]</code> 凑 <code>11</code> 的最优答案是 <code>5+5+1</code>，只需要 3 张。