322. 零钱兑换(难度:中等)
程序员文章站
2022-04-24 16:28:36
...
322. 零钱兑换(难度:中等)
题目链接:https://leetcode-cn.com/problems/coin-change/
问题描述:
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1
。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
解法一:动态规划 + 剪枝
首先,看见题目,我们一定先想到的是递归算法,我们分析这道题,他是具备 最优子结构 的。
最优子结构:
一个大问题的最优结果是由一堆子问题的最优结果推导出来的。比如我们要计算17的最少硬币数量,如果我们知道了16的最少硬币数是3枚(10,5,1),那么就把子问题的结果+1(再加一枚1元的硬币)就是原问题的答案。
满足的条件:硬币的数量没有现在,子问题之间没有任何限制,都是相互独立的。
重叠子问题:
应该在计算过程中,可能会对一个子问题进行反复的求解,比如我们可以会把子问题所需的最少硬币组成重复计算,这时候我们可以使用一个数组list来记录已经计算过的子问题结果,相当于一个备忘录的功能。
状态转换方程:
我们分解子问题的过程,对原问题需要面值amout,每次选取一枚硬币面值t,然后使用硬币数目+1,再计算面值amout-t所需要的最少硬币数目。
当我们在分解子问题的过程中,可以会遇到以下几种情况:
(1)当子问题需要计算的面值为0,则不再需要硬币,返回0;
(2)当子问题需要计算的面值小于-1,显然是不满足条件的,返回-1;
(3)当子问题需要计算的面值大于0时,则所需硬币数+1,继续分解子问题。
代码:
public class Solution {
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
return coinChange(coins, amount, new int[amount]);
}
private int coinChange(int[] coins, int rem, int[] count) {
if (rem < 0) return -1;
if (rem == 0) return 0;
if (count[rem - 1] != 0) return count[rem - 1];
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int res = coinChange(coins, rem - coin, count);
if (res >= 0 && res < min)
min = 1 + res;
}
count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
return count[rem - 1];
}
}
下一篇: 945. 使数组唯一的最小增量