给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
例子
输入：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
提示：
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000
解题思路
典型的动态规划问题, 它利用了之前计算的结果来更新当前的结果，这是动态规划的典型特点。
初始化： 我们创建一个数组 dp，长度为 amount + 1，用来存储每个金额对应的组合数。
dp[0] 初始化为: 1，因为凑成金额 0, 只有一种，即不用任何硬币。
遍历硬币： 我们遍历给定的硬币数组 coins。对于每个硬币 coin，我们更新 dp 数组。
更新 dp 数组：
- 对于每个硬币
coin，我们从coin开始遍历dp数组，直到amount。 - 对于每个金额
i，我们更新dp[i]的值。 - 更新规则是
dp[i] = dp[i] + dp[i - coin]。这意味着凑成金额 i 的组合数等于之前计算的组合数(dp[i])加上凑成金额i - coin的组合数(dp[i - coin])。
对于每个硬币，我们可以选择使用它或不使用它。如果我们选择使用这个硬币，那么问题就变成了凑成金额 i - coin 的组合数，而i - coin 金额组合数在之前的步骤中计算过了。
返回结果： 最后，dp[amount] 就是我们要求的结果，即凑成总金额 amount 的组合数。
代码：
未翻译版
func change(_ amount: Int, _ coins: [Int]) -> Int {
var dp = [Int](repeating: 0, count: amount + 1)
dp[0] = 1
for coin in coins {
if coin > amount { return dp[amount] }
for i in coin...amount {
dp[i] += dp[i - coin]
}
}
return dp[amount]
}
翻译版
func change(_ amount: Int, _ coins: [Int]) -> Int {
// 定义0 ~ amount 的可变数组, 代表 0 ~ 总金额 之间的所有情况
var dp = [Int](repeating: 0, count: amount + 1)
// 凑成总金额为0 的时候, 只有1种可能, 不掏
dp[0] = 1
// 遍历硬币数组
for coin in coins {
// 如果当前硬币大于总金额, 直接返回 dp[amount]
// 例如: coins = [2], amount = 1 这种
// 或 coins = [2, 100, 101], amount = 3,
// 遍历到 100 这种, 超过要求总金额, 没必要继续遍历
if coin > amount { return dp[amount] }
// 遍历 当前硬币 ~ 总金额, 计算每种金额需要情况
for i in coin...amount {
// 凑成总金额 i 的方式
// 等于原来的组合数 加上凑成总金额 i - coin 的组合数
// 例如 coins = [1, 2, 3], amount = 5
// dp = [1, 0, 0, 0, 0, 0] 数组下标为对应总金额
// 当 i = 1, 硬币为1, 遍历完
// dp = [1, 1, 1, 1, 1, 1]
// 总金额如果是 0, 1种情况
// 总金额如果是 1, 1种情况
// ...
// 总金额如果是 5, 1种情况, 1+1+1+1+1
// 当 i = 2, 硬币为2, 须用2硬币
// 那么总金额为2的情况,
// 为当前总金额2组合数+总金额0组合数 2+0
// 即 dp[2] + dp[0],
// dp[2] = dp[2] + dp[2 - 2] = dp[2] + dp[0]
// 同理, 须用2硬币, 总金额为3的情况 2+1
// 为当前总金额3组合数+总金额1组合数 即 dp[3] + dp[1]
// dp[3] = dp[3] + dp[3 - 2] = dp[3] + dp[1]
// 同理, 须用2硬币, 总金额为4的情况 2+2
// 为当前总金额4组合数+总金额2组合数 即 dp[4] + dp[2]
// dp[4] = dp[4] + dp[4 - 2] = dp[4] + dp[2]
// 同理, 须用2硬币, 总金额为5的情况 2+3
// 为当前总金额4组合数+总金额3组合数 即 dp[5] + dp[3]
// dp[5] = dp[5] + dp[5 - 2] = dp[5] + dp[3]
dp[i] += dp[i - coin]
}
}
// 返回凑成总金额情况
return dp[amount]
}
时间复杂度:
，其中 n 是金额（amount）的大小，m 是硬币种类（coins 数组的长度）的数量。这是因为我们需要对每种硬币进行遍历，并且对每个金额从该硬币面额到总金额进行更新。
空间复杂度:
，其中 n 是金额（amount）的大小。我们需要一个长度为 n + 1 的数组来存储从 0 到 n 的每个金额对应的组合数。
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
网友评论