序言
虽然算法很难，但不应该就放弃。这是一个学习笔记，希望你们喜欢~
先自己尝试写，大概十几分钟仍然写不出来
看思路，再尝试跟着思路写
仍然写不出来，再看视频
b站up视频推荐：爱学习的饲养员
leetcode其他文章：
数组篇：
链表篇：
从小白开始刷算法 ListNode 链表篇 leetcode.203
从小白开始刷算法 ListNode 链表篇 leetcode.206
队列篇
从小白开始刷算法 ListNode 链表篇 leetcode.933
栈篇
从小白开始刷算法 Stack 栈篇 leetcode.496
哈希篇
从小白开始刷算法 Hash 哈希篇 leetcode.217
从小白开始刷算法 Hash 哈希篇 leetcode.705
树篇
从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144
从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94
从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94
堆篇
从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215
小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692
双指针篇
二分法篇
滑动窗口篇
递归篇
分治法篇
回溯法篇
dfs篇
bfs篇
并查集篇
记忆化搜索篇
记忆化搜索篇
难度：中等
题目：
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
题目来源：力扣（LeetCode）
递归+记忆化搜索 思路
能否写出：不能写出。
时间：一个小时起步
思路：
首先，判断如果目标金额amount小于1，则直接返回0，因为无法凑出金额小于等于0的情况。
- 创建一个大小为
amount+1的记忆数组memo，并初始化所有元素为-1，用于存储每个金额的最少硬币数。 - 调用递归函数
coinChangeRecursive，传入硬币数组coins、目标金额amount和记忆数组memo。 - 在递归函数中，首先判断如果目标金额
amount小于0，则返回-1，表示无法凑出该金额。 - 判断如果目标金额
amount等于0，则返回0，表示已经凑出了所需的金额，不需要继续递归。 - 检查记忆数组
memo，如果当前金额amount的最少硬币数已经计算过，则直接返回该值，避免重复计算。
接下来，初始化一个变量minCount，用于记录当前金额amount的最少硬币数，初始值设为最大整数。
然后，遍历硬币数组coins，对每个硬币进行操作：
- 计算剩余金额
remainingAmount，即目标金额amount减去当前硬币的面值。 - 递归调用
coinChangeRecursive函数，传入剩余金额remainingAmount和记忆数组memo，得到凑齐剩余金额所需的最少硬币数。 - 如果凑齐剩余金额的最少硬币数不等于-1，表示找到了有效的组合，更新
minCount为当前硬币数加上剩余金额的最少硬币数，并取最小值。 - 重复以上步骤，直到遍历完所有硬币。
最后，将计算得到的最少硬币数存入记忆数组memo中，如果minCount仍然等于初始值，则表示无法凑出目标金额，返回-1；否则返回minCount。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public int coinChange(int[] coins, int amount) { if (amount < 1) { return 0; } int[] memo = new int[amount + 1]; Arrays.fill(memo, -1); return coinChangeRecursive(coins, amount, memo); } private int coinChangeRecursive(int[] coins, int amount, int[] memo) { if (amount < 0) { return -1; } if (amount == 0) { return 0; } if (memo[amount] != -1) { return memo[amount]; } int minCount = Integer.MAX_VALUE; for (int coin : coins) { //目标金额amount中减去当前硬币后剩余的金额。 int remainingAmount = amount - coin; //计算凑齐剩余金额所需的最少硬币数 int count = coinChangeRecursive(coins, remainingAmount, memo); //这行代码检查是否找到了一个有效的硬币组合来凑齐剩余金额。 //如果count不等于-1（表示找到了有效的组合），则继续执行代码来更新minCount if (count != -1) { //这行代码更新minCount，取最小值，以确保记录最少硬币数的情况。 //将当前的minCount与count + 1（因为选择了当前硬币，所以硬币数需要加1）进行比较 minCount = Math.min(minCount, count + 1); } } //存入记忆数组中 memo[amount] = (minCount == Integer.MAX_VALUE) ? -1 : minCount; return memo[amount]; } }
时间复杂度：O(MN)
- 其中M为目标金额，N为硬币种类数，每个金额需要遍历硬币数组。
空间复杂度：O(N)
- 记忆数组的大小与目标金额N相关
