LeetCode322.零钱兑换（一）

本文主要是介绍LeetCode322.零钱兑换（一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

LeetCode刷题记录

文章目录

- 📜题目描述
- 💡解题思路
- ⌨C++代码

📜题目描述

给你一个整数数组 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 最少需要的硬币枚数