【剑指offer进阶|剑指offer103（最少的硬币数目）】题目：
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例一：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例二：
输入：coins = [2], amount = 3
输出：-1
示例三：
输入：coins = [1], amount = 0
输出：0
示例四：
输入：coins = [1], amount = 1
输出：1
示例五：
输入：coins = [1], amount = 2
输出：2
分析：
将每种面额的硬币看成一种物品，而将目标金额看成背包的容量，那么这个问题等价于求将背包放满时物品的最少件数，值得注意的时这里每种面额的硬币可以使用任意多次，因此这个问题不再是0-1背包问题了，而是一个无界背包问题。（也叫完全背包问题）
用函数f(i,j)表示前i种硬币（coins[0,…,i-1]）凑出总额为j需要的硬币的最少数目，当使用0枚标号为i-1的硬币时，f(i,j)=f(i-1,j)，当使用1枚标号为i-1的硬币时，f(i,j)等于f(i-1,j-coins[i-1])+1,以此类推当使用k枚标号为i-1的硬币时，f(i,j)等于f(i-1,j-kcoins[i-1])+k（用前i-1种硬币凑出总额j-kcoins[i-1]需要的最少硬币数目，再假设k枚标号为i-1的硬币），由于目标时求出硬币数目的最小值，因此f(i,j)是上述所有情况的最小值：
文章图片
如果硬币有n种，目标总额为t，那么f(n,t)就是问题的解。
当j=0时也就是总额为0时，f（i，0）=0，也就是从前i种硬币中选出0个硬币，使总额等于0.当i等于0且j大于0时，即用0种硬币凑出大于0的总额显然不可能因此可以用一个特殊值代替。
第二种思路：
文章图片
之前相当于横着从右往左计算，这种方式类似从上往下算，算完一列再算下一列，用函数f(i)表示凑出总额为i的硬币需要的最少数目，需要注意的是，这个函数只有一个参数i表示硬币的总额，如果目标总额为t那么f(t)就是整个问题的解。
代码：
import java.util.Arrays;
public class CoinChange {
//第一种思路
public int coinChange1(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp,amount+1);
dp[0] = 0;
for (int coin : coins) {
for (int j = amount;
j >=1;
j--) {
for (int k = 1;
k*coin <=j;
k++) {
dp[j] = Math.min(dp[j],dp[j-k*coin]+k);
}
}
}
return dp[amount] > amount ?-1:dp[amount];
}
//第二种思路
//
public int coinChange2(int[] coins, int amount){
int[] dp = new int[amount+1];
//i代表总额，dp[i]代表凑出总额为i的最少硬币数目
for (int i = 1;
i <=amount;
i++) {
dp[i] = amount+1;
for (int coin:coins){
//如果总额度大于等于该硬币的值
if (i>=coin){
dp[i] = Math.min(dp[i],dp[i-coin]+1);
}
}
}
return dp[amount]>amount ?-1:dp[amount];
}
}
文章图片
推荐阅读
- 剑指offer进阶|剑指offer85（生成匹配的括号）
- 蓝桥杯|蓝桥杯——乳草的入侵
- #|算法Day6（广度优先搜索——最短路径问题）
- 动态规划|dp+贪心+滚动数组优化——植物大战僵尸
- 论文解读|Query-Efficient Hard-label Black-box Attack: An Optimization-based Approach论文解读
- leetcode|《九日集训》(第九讲) 简单递归
- 人工智能|一文看懂CV中的注意力机制
- Java进阶|Java进阶学习——数据结构基础（二）
- 数据结构|小肥柴慢慢手写数据结构（C篇）（3-2 Stack应用举例）