首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

为什么这个递归函数不能计算找零的硬币数量?

递归函数不能计算找零的硬币数量的原因可能有以下几点:

  1. 缺少基准情况(递归终止条件):递归函数需要定义一个基准情况,即当输入满足某个条件时直接返回结果,而不再进行递归调用。在找零的硬币数量问题中,可能没有定义基准情况,导致递归函数无法终止。
  2. 递归调用参数错误:递归函数在每次调用自身时,需要传入不同的参数,以便问题规模逐渐减小。在找零的硬币数量问题中,可能没有正确地传入递归调用的参数,导致递归无法进行。
  3. 递归调用过程中的状态更新错误:在递归函数中,可能需要更新某些状态变量,以便正确计算结果。在找零的硬币数量问题中,可能没有正确地更新状态变量,导致结果计算错误。
  4. 递归函数的时间复杂度过高:递归函数在某些情况下可能会导致指数级的时间复杂度,使得计算过程非常耗时甚至无法完成。在找零的硬币数量问题中,如果递归函数的时间复杂度过高,可能无法在合理的时间内得到结果。

针对这个问题,可以尝试以下改进措施:

  1. 确定递归函数的基准情况:在找零的硬币数量问题中,可以定义当目标金额为0时,返回0作为基准情况。
  2. 正确传入递归调用的参数:在找零的硬币数量问题中,可以在每次递归调用时,将目标金额减去当前硬币面额作为新的目标金额传入递归函数。
  3. 更新状态变量:在找零的硬币数量问题中,可以使用一个变量来记录已经使用的硬币数量,并在每次递归调用时进行更新。
  4. 考虑使用动态规划等其他算法:如果递归函数的时间复杂度过高,可以尝试使用其他算法来解决找零的硬币数量问题,例如动态规划算法。

需要注意的是,以上改进措施仅为一种可能的解决方案,具体的改进方法还需要根据实际情况进行调整。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

js算法初窥05(算法模式02-动态规划与贪心算法)

这么说有点懵逼....那么我们试试用动态规划来解决一些经典问题。 一、最少硬币找零问题 最少硬币找零问题是硬币找零问题一个变种。...硬币找零问题是给出要找零钱数,以及可用硬币面额以及对应数量,找出有多少种找零方法。最少硬币找零问题则是要找出其中所需最少数量硬币。...毕竟有了计算机很快速简单就可以得到结果,不用我们再费力地用人脑去解决问题了,下面我们就来看一下代码: //最少硬币找零 function MinCoinChange(coins) { // coins...这个问题有两个版本,一个是0-1背包问题,该版本只允许背包里装入完整物品,不能拆分。还有另外一个是可以装入分数物品。我们后面会用贪心算法来解决分数背包问题。   ...所以我们可以这样(A(B(CD))),或者这样((AB)(CD))等五种相乘方法,但是要注意是,每种相乘顺序不一样,我们计算量也是不一样。所以,我们来构建一个函数,找出计算量最少相乘方法。

1K30

js算法初窥05(算法模式02-动态规划与贪心算法)

这么说有点懵逼….那么我们试试用动态规划来解决一些经典问题。 一、最少硬币找零问题 最少硬币找零问题是硬币找零问题一个变种。...硬币找零问题是给出要找零钱数,以及可用硬币面额以及对应数量,找出有多少种找零方法。最少硬币找零问题则是要找出其中所需最少数量硬币。...毕竟有了计算机很快速简单就可以得到结果,不用我们再费力地用人脑去解决问题了,下面我们就来看一下代码: //最少硬币找零 function MinCoinChange(coins) { // coins...这个问题有两个版本,一个是0-1背包问题,该版本只允许背包里装入完整物品,不能拆分。还有另外一个是可以装入分数物品。我们后面会用贪心算法来解决分数背包问题。   ...所以我们可以这样(A(B(CD))),或者这样((AB)(CD))等五种相乘方法,但是要注意是,每种相乘顺序不一样,我们计算量也是不一样。所以,我们来构建一个函数,找出计算量最少相乘方法。

25720

动态规划(二)

四、硬币找零问题 给你不同面值硬币和金额总额。写一个函数计算需要最少数量硬币。...如果钱不能由当前硬币组合,返回-1 我们首先提炼这个问题特征,①硬币可重复多次使用,②对于每一枚硬币,都有两种决策,选或者不选。...其实只要在你选择这个硬币之后,idx不加1,这样下次就还是拿这种硬币。...第二,无法找零情况,要返回-1,但是我们这里有加1,可能导致最后输出值不是-1,而我们要求是使用最少硬币数量,那我们干脆定义一个最大值maxvalue,然后在主函数中进行if判断,见下图...图5-2递归式2 其实都是一样,只不过这个是从后往前考虑,而且读者应该能发现,这道题递归式跟LCS这题非常相似 image.png 图5-3编辑距离DP代码 六、最长公共子序列(LCS)

59640

浅析常见算法范式

分而治之是一种常见算法设计,它思路是把问题分解为与原始问题相似的较小子问题。通常以递归方式解决子问题,并结合子问题解决方案来解决原始问题。...动态规划案例:最小硬币找零问题 这是一个名为为硬币找零问题常见面试题。硬币找零问题是给定找零金额,找出可以用多少特定数量硬币找零方式。...最小硬币找零问题只是找到使用给定面额钱所需最少硬币数量。例如,如果需要找零 3 毛 7 分,则可以使用 1 个 2 分,1个 5 分,1 个 1 毛钱和1个 2 毛钱。...为了防止重复计算,用到了一个 cache 。makeChange 函数递归实现,它是一个内部函数,可以访问 cache。...贪心算法倾向于简单直观,但可能不是整体最优解决方案。 贪心算法案例:最小硬币找零问题 上面用动态规划解决硬币问题也可以用贪心算法解决。这个解决方案是否能得到最优解取决于所采用面额。

86021

猴子摘香蕉问题python_硬币找零&&爬楼梯&&猴子摘香蕉「建议收藏」

大家好,又见面了,我是你们朋友全栈君。 硬币找零&&爬楼梯&&猴子摘香蕉 假设有几种硬币,如1、3、5,并且数量无限。请找出能够组成某个数目的找零所使用最少硬币数。...” #include intmain(){ intcoin[3]={1,3,5}; CoinProblem(coin,3,5,0); std::cout< } 这些问题都是一类问题,你猴子摘香蕉、硬币找零...这类问题共同点就是你要问题解决问题,也就是说你要恰好把问是不多不少地解决,不管你怎么摘香蕉,不管你一次 是摘几个,你得把香蕉摘完。你得恰好找别人那么钱,不能多也不能少。爬楼梯也一样啰。。...这个不像背包问题,因为背包是不一定能装满,也就是结束条件是不确定。 但是我们不要管是不是恰好,因为我们采用了梯归。...因为递归好处是把所有能考虑问题都考虑了,包括恰好解决问题和 把问题所要求多,或者少。。

28850

动态规划快速入门

重叠子问题:在用递归算法自顶向下解问题时,每次产生子问题并不总是新问题,有些子问题被反复计算多次。...如果画出递归图(像二叉树一样),会发现有很多很多重复节点。然而传统递归算法并不能识别节点是不是重复,只要不到终止条件,它就会一直递归下去。...你公司正设法在每一笔交易 找零时都能提供最少数目的硬币以便工作能更加简单。已知硬币有四种(1美分,5美分,10美分,25美分)。...假设一个顾客投了1美元来购买37美分物品 ,你用来找零硬币最小数量是多少? 建立模型: 最优子结构:回想找到最优子结构方法,就是往后退一步,能够得到最好结果。...状态转移方程:按照上述最优子结构,mincoins(63)也就等于上述四个最优子结构最小值。 边界: 当需要找零面额正好等于手中单枚硬币金额时,返回1即可。

43620

算法奥秘:常见六种算法(算法导论笔记2)

动态规划算法: 动态规划算法用于解决最优化问题,通过将问题分解为若干个子问题,并记录子问题解,从而避免重复计算,提高求解效率。常见动态规划算法包括背包问题、最大子段和问题等。...这种策略虽然不一定能找到最优解(即使用最少数量钱币),但通常能找到一个接近最优解结果。 贪心算法优点在于它每一步操作都非常简单明了,也容易实现。...因此,当我们使用贪心算法时,需要先判断它是否适用于当前问题。 这个算法首先将硬币按照面值从大到小排序,然后从面值最大硬币开始找零,尽可能多地使用这种硬币,直到找零金额无法再使用这种硬币为止。...然后,算法使用下一种面值较大硬币,重复上述过程,直到找零金额减到0为止。...在实现中,我们将硬币按照面值从大到小排序,然后依次枚举每种硬币计算使用这种硬币能够找零多少金额,然后将这种硬币加入结果列表中。重复这个过程,直到找零金额减到0为止。

16910

TypeScript实现贪心算法与回溯算法

最少硬币找零问题 最少硬币找零问题也可以用贪心算法来解决,大部分情况下结果都是最优,不过对于有些面额而言,结果不会是最优。...实现思路 需要两个参数:硬币面额coins、找零金额amount 声明辅助变量change,用于存储找零方案 声明辅助变量total,用于存储当前已找零金额 从大到小遍历coins 取出当前遍历到面额...每个位置值为0或1 0表示这个格子有障碍物不能走,1表示这个格子为空闲状态可以走 如下表所示为一个矩阵,其中S是起点,D是重点 S D 矩阵就是迷宫,老鼠目标就是从S位置移动到...,即y+1,用新递归调用寻找路径函数。...我们来看看递归函数实现。

73730

TypeScript 实战算法系列(十):实现动态规划

算法思想 这个方法可以分为三个部分: 分解,将原问题划分为多个子问题。 解决,用返回解决子问题方式递归算法将子问题解决。 组合,组合这些子问题解决方式,得到原问题解。...最少硬币找零问题 最少硬币找零问题就是:给定一个找零总金额和一组若干个面值硬币,用给出硬币面值去找零,怎么样找零需要硬币个数最少。...声明一个函数(minCoinChange),其接收两个参数:硬币面额coins其类型为数组,找零总金额amount其类型为数字 声明一个二维数组cache用于存储已经找到组合,防止递归计算时遇到已经计算过一遍出组合金额再次重复计算...函数内部声明递归函数(makeChange),其接受一个参数找零金额amount,用于将大问题划分为小问题,最终得到总问题答案,函数内部实现思路如下。...获取当前遍历到面值,即coin = coins[i] 用amount - coin就是newAmount值 如果计算出来newAmount值大于等于0就递归,即加入递归栈中 递归执行完成后,我们依次取出递归栈中数据

84120

TypeScript实现动态规划

算法思想 这个方法可以分为三个部分: 分解,将原问题划分为多个子问题。 解决,用返回解决子问题方式递归算法将子问题解决。 组合,组合这些子问题解决方式,得到原问题解。...最少硬币找零问题 最少硬币找零问题就是:给定一个找零总金额和一组若干个面值硬币,用给出硬币面值去找零,怎么样找零需要硬币个数最少。...声明一个函数(minCoinChange),其接收两个参数:硬币面额coins其类型为数组,找零总金额amount其类型为数字 声明一个二维数组cache用于存储已经找到组合,防止递归计算时遇到已经计算过一遍出组合金额再次重复计算...函数内部声明递归函数(makeChange),其接受一个参数找零金额amount,用于将大问题划分为小问题,最终得到总问题答案,函数内部实现思路如下。...获取当前遍历到面值,即coin = coins[i] 用amount - coin就是newAmount值 如果计算出来newAmount值大于等于0就递归,即加入递归栈中 递归执行完成后,我们依次取出递归栈中数据

68930

数据结构与算法入门手册

第二部分:常用算法类型 图片 递归算法:子问题解决依赖于递归算法,典型例子阶乘函数、斐波那契数列。需设置终止条件,否则会出现栈溢出。 贪心算法:在当前选项中做最佳选择,典型例子硬币找零、最小生成树。...递归算法:通过递归解决子问题,典型例子阶乘函数、斐波那契数列。需设置终止条件,否则栈溢出。...n) {if (n == 1 || n == 2) return 1; else return fib(n-1) + fib(n-2);} 贪心算法:在当前做最佳选择,典型例子硬币找零、最小生成树。...硬币找零:每次取面值最大硬币,直到零钱数为0。 Prim算法:每次选取与当前树相连权值最小边,直到所有点被选取。 分治算法:通过递归将问题划分为相同或相似子问题,典型例子二分查找、快速排序。...KMP算法:通过生成前缀函数 skipi表示模式串中i之前字符串中最长相同前后缀长度, 降低回溯次数。 排序:给元素序列按一定顺序进行排列。

53240

硬币找零问题

硬币找零问题是一种经典背包问题。 顾名思义,就是你去商店买完东西,售货员会给你用若干枚硬币找钱,如何使用这些硬币完成找零。...问题一:组成当前值所需最少硬币数目 给定不同面额硬币 coins 和一个总金额 amount。编写一个函数计算可以凑成总金额所需最少硬币个数。...2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2: 输入: coins = [2], amount = 3 输出: -1 说明: 你可以认为每种硬币数量是无限...该问题一个简化版,当一个大面值硬币总是可以由小面值硬币组合而成时(即参考软妹币),可以使用一种贪心策略即优先使用大面值直到不能使用再使用小面值,如此即为最少硬币花费数目。...-1 : dp[amount]; } } 上述为空间压缩之后代码。 问题二:凑成当前值组合数目 给定不同面额硬币和一个总金额。写出函数计算可以凑成总金额硬币组合数。

1.3K20

【基础算法】贪心算法

这3种硬币数量不限,现在要找给顾客2元7角。请问怎样才能使得找给顾客硬币数量最少?...按照这个策略,最终找给顾客硬币数量就是最少。 贪心算法每一步只考虑局部最优解,所以在处理问题时候可能得不到整体最优解。...贪心算法时间复杂度为 O(n^2) ,其中n为广播台数量。 首先是函数声明部分,我们要传入所有的州,所有的广播台以及每个广播台所能覆盖到州。...总结 这三道贪心算法都包含递归特性,处理下一步方法与处理上一步类似: 找零钱中是递归地寻找剩余零钱允许最大硬币。 分薄饼是递归地寻找最小需求(人)最小需求(饼)。...这并非偶然,这一递归特征已经隐含在贪心算法定义中:不断地寻找局部最优解。 如果将寻找局部最优解过程封装为函数,在函数结尾调用自身,寻找下一个局部最优解。那么就变成了一个递归算法。

28140

动态规划应用--找零

问题描述 找零问题,在贪心算法讲过。但是贪心不一定能得出最优解。假设有几种不同币值硬币v1,v2,.……vn(单位是元)。如果要支付w元,求最少需要多少个硬币。...比如,有3种不同硬币,1元、3元、5元,我们要支付9元,最少需要3个硬币(3个3元硬币)。 2....} return; } for(int i = 0; i < N; ++i) {//递归调用,拿取每张面额钞票 amount[...2.2 DP状态转移方程法 由于上面的钞票面额可能不止3种,递归树是多叉树,所以状态转移表法画起回溯递归图比较麻烦,我们采用状态转移方程法。...,表示不可能凑成 return 65535; if(Money == 0)//达到目标金额 return 0; if(mem[Money] > 0)//计算过了

63210

Leetcode-Medium 322. Coin Change

题目描述 假设给你不同面额硬币和一个金额amount。编写一个函数计算构成该金额amount所需最少数量硬币。如果这笔钱不能由任何硬币组合成,则返回-1。...不一定,因为如果取一枚金额为10硬币就足够了,此时dp[10]=dp[10-10]+1=0+1=1.所以我们需要在取me某一枚硬币之后,需要更新当前dp[i]值。...dp[i]=min(dp[i],dp[i-coin]+1) 另外我们需要初始化dp,假设每一个硬币面额都大于amount,此时我们是找不出硬币组合,那么dp[amount]=-1,显然我们不能初始化所有值为...-1(负数小于任何正数),我们应该初始化一个“最大值”,比如inf或者amount+1,当遍历所有金额之后,最后dp[amount]仍然为'最大值',说明这笔钱不能由任何硬币组合成,那么我们返回-1。...Coin Change Java – Bear熊 – Medium [LeetCode] Coin Change 硬币找零 - Grandyang - 博客园 LeetCode 322.

73620

C++ 不知算法系列之深入动态规划算法思想

2.1.2 问题分析 动态规划是一种从下向上解决方案,也就是逆推思维。 顺着这个思路,本题目可以先计算离E最近D层到E最短路程。D层上有 3 个顶点,意味着需要单独计算 3 次。...:"<< db[i]<<endl; } return 0; } 输出结果: 2.2 找零钱 2.2.1 问题描述 给你k种面值硬币,面值分别为c1, c2 ... ck,每种硬币数量无限,再给一个总金额...amount,问最少需要几枚硬币凑出这个金额,如果不可能凑出,算法返回 -1 。...当找零为 6 时,也有 2 种方案,先拿出一枚 1 分硬币,再计算剩下 5 分钱最少需要找回多少硬币。另一个方案就是拿出一枚 5分硬币计算剩下 1 分钱需要找回最少硬币。...其中第i个物品重量为wt[i],价值为val[i],现在用这个背包装物品,最多能装价值是多少? Tips: 题目中物品不可以分割,要么装进包里,要么不装,不能切成两块装一半。

41610

PAT--L3-001. 凑零钱

现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球硬币付钱,但是绝不找零,当然也不能欠债。...韩梅梅手边有104枚来自各个星球硬币,需要请你帮她盘算一下,是否可能精确凑出要付款额。 输入格式: 输入第一行给出两个正整数:N(<=104)是硬币总个数,M(<=102)是韩梅梅要付款额。...第二行给出N枚硬币正整数面值。数字间以空格分隔。 输出格式: 在一行中输出硬币面值 V1 <= V2 <= … <= Vk,满足条件 V1 + V2 + … + Vk = M。...,则直接返回,即剪枝 if(surm||flag||step>n||m<val[step]) { return; } // 如果选中硬币价值等于目标价值,那么输出并且结束递归...if(sum==m) { //cout<<"YES"<<endl; print(); flag=true; return; } // 如果这个硬币选中了

68740

javascript经典算法之最小硬币找零问题

正文 笔者抽空总结了几个比较经典且实用算法, 最少硬币找零问题 是本文介绍第一道算法题: 问题:给出要找零钱数amount以及可用硬币面额c1, c2, c3, ..., 求所需最少硬币个数。...思考这道问题可以有很多不同思路, 笔者主要采用两种方法来解决这个问题: 1. 动态规划法 2. 贪心算法 接下来笔者具体介绍这两种算法思路和实现代码. 1....硬币找零问题也可以用该思想来解决,首先按照正常逻辑,我们可以先计算在给定金额amount和给定面额下,一共有几种找零方法,然后求出长度最短找零方案。...若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止。...,从而实现总硬币数最小目的。

1.5K20

【地铁上面试题】--基础部分--数据结构与算法--动态规划和贪心算法

通过调用这些函数,可以计算出给定图中顶点之间最短路径长度。...五、贪心算法实现和应用 5.1 零钱找零问题 零钱找零问题是一个经典贪心算法问题,要求在给定一定面额硬币和一个要找零金额时,找出最少硬币数量来组成该金额。...当找零金额变为0时,表示找零完成,返回硬币数量count。...25}; // 硬币面额 int n = sizeof(coins) / sizeof(coins[0]); // 硬币数量 int amount = 37; // 要找零金额...{ printf("最少需要硬币数量为:%d\n", result); } return 0; } 以上代码通过贪心算法思想,从面额最大硬币开始逐步找零,直到找零金额变为

29620
领券