牛客热题：兑换零钱(一)

本文主要是介绍牛客热题：兑换零钱(一)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：兑换零钱(一)

题目链接

兑换零钱(一)_牛客题霸_牛客网 (nowcoder.com)

方法一：动态规划

思路

首先我们思考当arr中最小的零钱是1时，那么这时候是凑成aim的最大钱数，aim个1块钱。

①状态表示：

​ $dp[i]$表示的是i块钱用数组中的零钱表示的最少钱数。

②状态转化：

​ 显然$dp[i]$的值可以从$dp[i-arr[j]]$的状态获取，但是题目要求最小值，所以取一个min

​ $dp[i]=min(dp[i],dp[i-arr[j]]+1)$

③填表顺序：

​ 对于dp数组的话，因为dp的当前状态需要用到之前状态，所以按照从左的到右的顺序

​ 对于原数组arr，这个数组的话不牵扯到状态转移，只需要遍历就好了，习惯上也从左到右来遍历

④初始化：

对于dp数组，开始时除了$dp[0]=0$,其余的dp状态都应该设定为对应的最大值+1，也就是aim + 1；

⑤返回值：

代码

    int minMoney(vector<int>& arr, int aim) {//创建dp数组vector<int> dp(aim + 1, aim + 1);dp[0] = 0;for(int i = 0; i <= aim; ++i){for(int j = 0; j < arr.size(); ++j){if(i >= arr[j])dp[i] = min(dp[i], dp[i - arr[j]] + 1);}}return dp[aim] > aim ? -1 : dp[aim];}

复杂度

时间复杂度：$O(aim\ast arr.size())$, 遍历dp数组的同时去遍历原数组。

空间复杂度：$O(aim+1)$,额外使用了一个dp数组，长度是aim+1。

方法二：递归

思路

1. recursion 函数：

   • 这是一个递归函数，用于计算组合达到目标金额 aim 所需的最小硬币数量。
   • 参数包括 arr（硬币面值数组）、aim（目标金额）、dp（用于记录中间结果的数组）。

2. 基础情况：

   • 如果 aim < 0，表示当前的组合方式超过了目标金额，返回 -1。
   • 如果 aim == 0，表示当前的组合方式正好等于目标金额，返回 0（硬币数量为0）。
   • 如果 dp[aim - 1] != 0，说明 aim 这个金额已经计算过了，直接返回 dp[aim - 1]。

3. 递归求解：

   • 初始化 Min 为 INT_MAX，用于记录当前情况下的最小硬币数量。
   • 遍历所有硬币面值 arr[i]，对于每个面值，计算使用该面值时剩余金额 aim - arr[i] 的最小硬币数量 res。
   • 如果 res >= 0（说明可以组合成功）且 res + 1 比当前 Min 小，则更新 Min。

4. 更新结果：

   • 将 dp[aim - 1] 设置为 Min，如果 Min 仍然是 INT_MAX，表示无法组合成 aim，返回 -1，否则返回 Min。

5. minMoney 函数：

   • 这是主函数，初始化了 dp 数组并调用了 recursion 函数来求解最小硬币数量。
   • 如果 aim < 1，直接返回 0，因为小于等于 0 的金额不需要硬币。

总结思路：

• 使用递归方法和动态规划思想，通过 dp 数组记录中间结果，避免重复计算，提高效率。
• 递归函数中每次选择一个硬币面值，尝试组合达到目标金额，找出最少的硬币数量。
• 如果某个金额已经计算过，直接返回已存储的结果，避免重复计算，提高效率。

代码

    int recurison(vector<int>& arr, int aim, vector<int>& dp){if(aim < 0) return -1;if(aim == 0) return 0;if(dp[aim - 1] != 0)return dp[aim - 1];int Min = INT_MAX;//遍历所有的值for(int i = 0; i < arr.size(); ++i){//递归运算选择当前的面值int res = recurison(arr, aim - arr[i], dp);//获取最小值if(res >= 0 && res < Min)Min = res + 1;}//更新最小值dp[aim - 1] = Min == INT_MAX ? -1 : Min;return dp[aim - 1]; }int minMoney(vector<int>& arr, int aim) {if(aim < 0) return -1;vector<int> dp(aim, 0);return recurison(arr, aim, dp);}

复杂度

• 时间复杂度:$O(n\ast aim)$，一共需要计算aim个状态的答案，每个状态需要枚举n个面值
• 空间复杂度:$O(aim)$，递归栈深度及辅助数组的空间

这篇关于牛客热题：兑换零钱(一)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---