交易平台网站怎么做,WordPress的Ajax插件,云服务器免费虚拟主机,高水平建设专业网站大家好#xff01;我是曾续缘#x1f92a; 今天是《LeetCode 热题 100》系列 发车第 85 天 动态规划第 5 题 ❤️点赞 #x1f44d; 收藏 ⭐再看#xff0c;养成习惯 零钱兑换 给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount 我是曾续缘 今天是《LeetCode 热题 100》系列 发车第 85 天 动态规划第 5 题 ❤️点赞 收藏 ⭐再看养成习惯 零钱兑换 给你一个整数数组 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 121 coins[i] 231 - 10 amount 104 难度 解题方法
我们可以使用动态规划来解决这个问题。首先创建一个长度为 amount 1 的数组 dp其中 dp[i] 表示凑齐金额 i 所需要的最少硬币个数。初始化将 dp 数组所有元素值设为 amount 1这个值相当于无穷大用来表示不可能凑齐该金额。
然后我们从金额 1 开始遍历到 amount对于每个金额 i再遍历硬币数组 coins 中的每个硬币面额 coins[j]。如果当前硬币面额 coins[j] 小于等于当前金额 i则更新 dp[i] Math.min(dp[i], dp[i - coins[j]] 1)即当前金额 i 所需的最少硬币个数为当前值和减去当前硬币面额后的金额所需硬币个数加一的较小值。
最终返回 dp[amount]如果其值大于 amount表示无法凑齐该金额返回 -1否则返回 dp[amount]。
Code
public class Solution {public int coinChange(int[] coins, int amount) {// 初始化最大值为 amount 1int max amount 1;// 创建 dp 数组记录凑齐各个金额所需的最少硬币个数int[] dp new int[amount 1];// 将 dp 数组所有元素值设为 maxArrays.fill(dp, max);// 初始金额为 0 时所需硬币个数为 0dp[0] 0;// 遍历金额从 1 到 amountfor (int i 1; i amount; i) {// 遍历硬币数组for (int j 0; j coins.length; j) {// 如果当前硬币面额小于等于当前金额if (coins[j] i) {// 更新最少硬币个数dp[i] Math.min(dp[i], dp[i - coins[j]] 1);}}}// 返回最终结果若大于 amount 则无法凑齐返回 -1否则返回 dp[amount]return dp[amount] amount ? -1 : dp[amount];}
}
