零钱兑换
- 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
解题思路
这个问题可以使用动态规划来解决
-
1、我们定义一个长度为 amount+1 的数组 dp,其中 dp[i] 表示凑成金额 i 所需的最少硬币数量。
-
动态规划的状态转移方程为:
-
dp[i] = min(dp[i], dp[i - coin] + 1),
-
其中 coin 表示硬币的面额,且 coin <= i
这个方程的意思是,如果当前的金额 i 可以由硬币的面额 coin 和金额 i - coin 组成,那么 dp[i] 就可以通过 dp[i - coin] + 1 来更新,即将 coin 加入到凑成金额 i 的硬币组合中。
-
2、初始化数组dp,长度为amount + 1,全部初始化为amount + 1。
-
3、设置dp[0]为0,表示凑成金额0所需的最少硬币个数为0。
-
4、使用循环遍历从1到amount的每个金额i,内层循环遍历硬币数组coins,更新dp[i]为dp[i - coin] + 1和dp[i]中的较小值,其中coin为硬币的面额。
-
5、如果dp[amount]的值仍然为amount + 1,说明无法凑成总金额,返回-1,否则返回dp[amount]。
java实现
public class CoinChange {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
public static void main(String[] args) {
CoinChange cc = new CoinChange();
int[] coins = {1, 2, 5};
int amount = 11;
System.out.println("Minimum number of coins: " + cc.coinChange(coins, amount)); // Output: 3 (11 = 5 + 5 + 1)
}
}
时间空间复杂度
-
时间复杂度:外层循环遍历了amount次,内层循环遍历了硬币数组coins,时间复杂度为O(amount * coins.length)。
-
空间复杂度:使用了长度为amount + 1的数组dp,空间复杂度为O(amount)。