每日手撕一道算法题-322.零钱兑换
每日手撕一道算法题-322.零钱兑换
322. 零钱兑换
题目：
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1示例 2:
输入: coins = [2], amount = 3
输出: -1解析
举例面值是1，2，5
可以逆推。凑11最少的硬币数 = 凑10最少的硬币数/凑9最少的硬币数/凑6最少的硬币数 中最少的那个
凑10最少的 = 凑9最少的 / 凑8最少的 / 凑5最少的 最少的那个
依次循环
转成正向思路是，开辟长度12的数组。0号索引值放0。
后面数组索引代表凑的目标值。
1号索引，求凑1的最少个数，遍历面值1，2，5。因为目标值1-硬币1>=0。目标值1-硬币1 = 剩余值。
而剩余值 >= 0。说明数组中有结果，可以直接用。用凑剩余值的最少个数+1即为凑1的个数。
凑2也是这样。 i 是索引值，也是要凑的目标值。如果 目标值 - 硬币面值coin = 剩余值 。剩余值 >= 0，说明
剩余值 在之前的数组中。直接使用剩余值的结果 + 1即可。然后去 这些最少的那个。就是凑2的最优解。
后面的依次这样。
直到11号索引结束。如果11号索引不是我们一开始赋的初值，则说明有答案，返回答案。如果还是赋的初值，则返回-1没结果。
另外提一句，每个值初始值 除了第一个数是0，其余为amt+1。
是因为有个变态数据
[1],0。如果赋值为amt，则初值为0。
最后
memo[amt] == amt ? -1 : memo[amt];
结果 因为memo[0] 本来就是0。这个会满足返回 0 而不是-1。所以初值为amt+1。
一开始我想初始值赋为最大值的，结果发现还是有问题，有个数据 执行到
memo[i] = Math.min(memo[i], memo[i - coin] + 1);
因为 memo[i - coin] = 2147483647 加一后变成-2147483648。成了最小值返回回去了。
代码
class Solution {
public int coinChange(int[] coins, int amt) {
// 动态规划
int[] memo = new int[amt + 1];
Arrays.fill(memo, amt + 1); // 每个值赋值12
memo[0] = 0;
for (int i = 1; i <= amt; i++) // 从1到11，计算需要的最少硬币数
for (int coin : coins)
if (i - coin >= 0)
memo[i] = Math.min(memo[i], memo[i - coin] + 1);
return memo[amt] == amt + 1 ? -1 : memo[amt];
}
}