【动态规划6】零钱兑换问题

经过本章节前5道题的练习，大家能体会到动态规划的核心在于： 状态定义 和 状态转移方程。其本质是通过分解问题，将复杂问题拆解为较小的子问题，并用递推关系求解。

1. 状态定义

题目要求是什么，我们就定义什么为状态。

题目描述：

给定一个整数数组 $coins$，其中 $coins[i]$ 表示一个面额为 $coins[i]$ 的硬币；再给定一个整数 $amount$，表示你需要组成的总金额。请你计算组成该金额所需的最少硬币个数。如果没有任何一种硬币组合能够凑成该金额，返回 $-1$。

你可以假设每种硬币无数量限制。

输入

• 一个整数数组 $coins$，长度为 $n$，表示硬币的面额。$1 \leq n \leq 12$，$1 \leq coins[i] \leq 100$。
• 一个整数 $amount$，表示目标金额，满足 $0 \leq amount \leq 5000$。

输出

• 返回组成 $amount$ 的最少硬币个数。如果不能组成该金额，返回 $-1$。

示例

示例 1：

输入：

3
1 2 5
11

输出：

3

解释：通过选择 $5 + 5 + 1$，可以组成 $11$，所以最少需要 3 个硬币。

示例 2：

输入：

1
2
3

输出：

-1

解释：不能通过任何方式凑成 $3$。

提示

• 假设给定的硬币面额是有限的，且每个面额的硬币数量无限。