Leetcode 322 零钱兑换

计算机软件开发 · 2024-9-26 18:41:16

标题要求

给你一个整数数组 coins ，体现差别面额的硬币；以及一个整数 amount ，体现总金额。
盘算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能构成总金额，返回 -1 。
你可以以为每种硬币的数目是无穷的。
示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
表明：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

解题思路

这道题中的零钱数额是不固定的，以是须要用动态规划来办理。
dp体现构成金额 i 须要的硬币的个数。
动态转移方程：
dp = dp[i-k] + 1
起始状态：
dp[0] = 0
因为构成金额0须要 0个硬币。
Java题解

所属分类: 问答交流