Givemeyourmoney!!1「我的做题历程」：step1：观察题面。  「编写一个函数来计算可以凑成总金额」，可以得出这是一道背包DP。  「每种硬币的数量是无限的」，进一步得出这是道完全背包。（题型：完全背包）  「最少的硬币个数」，证明这要在背包的前提下，求出最小组成数量。  「多组测试数据」，谨记多组输入（论WrongAnswer与没有多组输入）。（注意：多组输入）step2：思考解法。  第一步，思考dp状态：\(dp_{i,j}\)：前\(i\)种硬币凑出面值\(j\)的最少币数。  对于当前一种硬币\(coins_{i}\)而言，只有取或不取两种状态。  若取，取后的币数为

题目描述给你一个整数数组arr，表示不同面额的硬币；以及一个整数aim，表示需要放入钱包的目标金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。每种硬币的数量无限。用例1：输入：[1,2,3],6输出：2（即3+3）思路一：深度优先搜索本题自然可以通过遍历所有可能的硬币组合以求得最少的硬币数量。每次都选择三种面额（以用例1举例）中的一枚放入到钱包中，直到钱包达到目标金额。上面这个思路其实就是深度优先搜索的方法（DFS）。递归深度就是使用的硬币的个数。然而这种方式将会出现大量的重复计算，比如用例中：6-2=4，6-1-1=4；导致4这个节点会被多

题目描述给你一个整数数组arr，表示不同面额的硬币；以及一个整数aim，表示需要放入钱包的目标金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。每种硬币的数量无限。用例1：输入：[1,2,3],6输出：2（即3+3）思路一：深度优先搜索本题自然可以通过遍历所有可能的硬币组合以求得最少的硬币数量。每次都选择三种面额（以用例1举例）中的一枚放入到钱包中，直到钱包达到目标金额。上面这个思路其实就是深度优先搜索的方法（DFS）。递归深度就是使用的硬币的个数。然而这种方式将会出现大量的重复计算，比如用例中：6-2=4，6-1-1=4；导致4这个节点会被多