518.零钱兑换 II
题目
给你一个整数数组 coins
表示不同面额的硬币,以及一个整数 amount
表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1:
输入:amount = 5, coins = [1, 2, 5] 输出:4 解释:有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2:
输入:amount = 3, coins = [2] 输出:0 解释:只用面额 2 的硬币不能凑成总金额 3 。
示例 3:
输入:amount = 10, coins = [10] 输出:1
提示:
coins
中的所有值互不相同
思路
- 确定dp数组及下标含义
用数组dp[j]
表示凑出总金额j
的硬币组合数。
- 递推公式
数组中的每个硬币,都可能采用也可能不采用, 采用某个硬币可记为coins[i]
。j - coins[i]
所需的硬币最少数量为dp[j - coins[i]]
, 在此基础上再加上一个硬币coins[i]
即dp[j - coins[i]] + 1
就可以得到dp[j]
。
但是采用的coins[i]
具体为哪个,需要遍历每个元素,求最小值。
所以递推公式为:dp[j] = min(dp[j - coins[i]] + 1)
- dp数组初始化
当要凑出的金额为0时,很明显dp[0] = 0
。
数组中的其他元素初始值该为多少?我们要求的是最小值,所以可以初始化一个比较大的值表示无穷大,在比较过程中会把大值淘汰掉。
多大合适呢?最好的办法为j + 1
,因为要凑出j
,不可能用j + 1
个硬币。
所以初始化dp[j] = j + 1
- 确定遍历顺序
本题求最小个数,有无顺序都不影响最小个数。 外层循环遍历dp,问题规模从小到大;内层循环遍历数组,遍历每个元素求最小值。
算法描述
import java.util.Arrays;
class Solution {
public int coinChange(int[] coins, int amount) {
// 定义dp数组
int[] dp = new int[amount + 1];
// 初始化dp数组
dp[0] = 0;
for (int j = 1; j < dp.length; j++) {
dp[j] = j + 1;
}
// 外层遍历背包
for (int j = 1; j <= amount; j++) {
// 内层遍历物品
for (int coin : coins) {
// 前序有解才可以
if (j >= coin && dp[j - coin] != j - coin + 1) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
}
// dp[amount] = amount + 1 表示无解
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}