力扣题目
解题思路
java代码
力扣题目:
给你一个整数数组 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
解题思路:
解法思路:
- 首先创建一个长度为
amount + 1
的整数数组dp
,用于保存每个金额对应的最少硬币数。 - 初始化
dp[0] = 0
,表示凑出金额为 0 不需要硬币。对于其他金额i
,先初始化为Integer.MAX_VALUE
,表示暂时无法凑出。 - 然后通过两层循环来计算每个金额的最少硬币数。外层循环遍历每个金额
i
,内层循环遍历每种面额的硬币coins[j]
。 - 如果当前金额
i
大于等于硬币面额coins[j]
,就尝试更新dp[i]
,取当前值和使用该硬币后(dp[i - coins[j]] + 1
)的较小值。
java代码:
package org.example.mouth7.today23;
public class Leetcode322 {
public static void main(String[] args) {
int[] coins = {1, 2, 5};
int amount = 11;
System.out.println(coinChange(coins, amount));
}
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
dp[i] = Integer.MAX_VALUE;
}
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (i >= coins[j]) {
dp[i] = Math.min( dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
标签:硬币,int,coins,示例,322,零钱,amount,Leetcode,dp From: https://blog.csdn.net/LIUCHANGSHUO/article/details/140625501更多详细内容同步到公众号,感谢大家的支持!
每天都会给刷算法的小伙伴推送明日一题,并且没有任何收费项