LeetCode322.零钱兑换（一）

LeetCode刷题记录

---

📜题目描述

给你一个整数数组 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

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

💡解题思路

amount为目标金额
我们定义一个[amount+1]大小的数组，dp[amount+1]

状态定义
dp[i]表示达到金额 i 所需要的最最少硬币枚数
每个状态所能加的钱数 只能是 coins 数组中的值
所有有些金额无法达到

以 coins = [1,2,5] ，amount = 11 为例
每个位置能走到 i + (one in coins) 位置，one in coins可以是 1、2、5

• 如果目标位置没到达过，目标位置的值为当前位置+1
• 如果目标位置到达过，目标位置的值 = min(目标位置当前值，当前位置+1)
• 如果当前位置不可到达，continue

状态转移
前提：i + coins[j] < length
若 dp[i + coins[j]] == -1 (即没有到达过此金额）
  dp[i + coins[j]] = dp[i] +1
否则
  dp[i + coins[j]] = min(dp[i+coins[j],dp[i]+1)

初始值
dp[0] = 0, 其余值初始化为 -1

返回结果
dp[amount] , 即为了凑成amount 最少需要的硬币枚数

⌨C++代码