leetcode|leetcode 322. Coin Change 零钱兑换(中等)
一、题目大意
标签: 动态规划
https://leetcode.cn/problems/coin-change
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11示例 2:
输出:3
解释:11 = 5 + 5 + 1
输入:coins = [2], amount = 3示例 3:
输出:-1
输入:coins = [1], amount = 0提示:
输出:0
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 231 - 1
- 0 <= amount <= 104
二、解题思路【leetcode|leetcode 322. Coin Change 零钱兑换(中等)】每个硬币可以用无限多次,所以是完全背包问题。
dp[i]表示,达到总金额i所需的最少硬币数,因为求最少硬币数所以先将dp初始化为amount+2,状态转移方程为:dp[i] = min(dp[i], dp[i-coin] + 1)
三、解题方法3.1 Java实现
public class Solution { public int coinChange(int[] coins, int amount) { if (coins.length == 0) { return -1; } int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 2); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i >= coin) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] == amount + 2 ? -1 : dp[amount]; } }
四、总结小记 - 2022/7/1 周五了,今天是个承上启下的日子
推荐阅读
- leetcode|leetcode 474. Ones and Zeroes 一和零(中等)
- Leetcode PHP题解--D138 35. Search Insert Position
- leetcode刷题|C++标准模板库方法STL和函数使用说明
- golang|LeetCode26 删除有序数组中的重复项 Go语言
- Leetcode|Leetcode 3. 无重复字符的最长子串
- LeetCode 3. 无重复字符的最长子串
- leetcode|leetcode 416. Partition Equal Subset Sum 分割等和子集(中等)
- 记录|leetcode刷题计划和每日刷题记录
- [LeetCode周赛复盘] 第 299 场周赛20220626
- [英雄星球六月集训LeetCode解题日报] 第24日 线段树