题目描述:
给定一个整数数组 coins,其中 coins[i] 表示一个面额为 coins[i] 的硬币;再给定一个整数 amount,表示你需要组成的总金额。请你计算组成该金额所需的最少硬币个数。如果没有任何一种硬币组合能够凑成该金额,返回 −1。
你可以假设每种硬币无数量限制。
【动态规划6】零钱兑换问题
经过本章节前5道题的练习,大家能体会到动态规划的核心在于: 状态定义 和 状态转移方程。其本质是通过分解问题,将复杂问题拆解为较小的子问题,并用递推关系求解。
1. 状态定义
题目要求是什么,我们就定义什么为状态。